**Goal:** –

**Course description:**

**Topics of Engineering**

1. Design and analysis of combination networks: universal logic functions, basics of systematic system design.

2. Description of combination networks: logic functions, truth tables, schematics and Karnaugh maps.

3. Ideal and realistic components, properties of real components: cause of non-ideal behavior, propagation delay, hazards in combination networks

4. Definition of sequential networks, classification of sequential networks.

5. Development and analysis of sequential networks: Basic latches, use and behavior of ip- ops, development of network from gates and latches.

6. Analysis of sequential networks, state-tables, state functions, state-diagrams, next-state maps. Race situation and oscillation in sequential networks.

7. Basic schematics of important logic network families and their properties, such as RTL, DTL, TTL, CMOS. Basic register schematics and basics of their operation.

8. Static and dynamic properties of digital circuits, properties of rising/falling edges and propagation delays, transfer characteristic of basic gates, static and dynamic power consumption.

**Topics of Software Design and Development**

You are expected to have general knowledge of the topics, to present examples, to present pseudocodes of relevant algorithms, to analyze algorithms’ efficiency, or occasionally provide C# code. There might be questions that involve several topics (e.g. compare the insertion sort, quicksort and heapsort algorithms).

1. The basics of algorithms

The concept of the algorithm, ow structures, tools for describing the algorithm (block diagram, box diagram, and pseudocode), efficiency, effectiveness, big O notation

2. Simple Basic Programs

BP Sequence, BP Decision, BP Selection, BP Linear Search, BP Counting, BP Maximum Search

3. Compound Basic Programs

BP Copy, BP Picking, BP Separation, BP Intersection, BP Union, BP Merge (union of sorted arrays)

4. Combining Basic Programs

Combining BP Copy with BP Maximum Search, Combining BP Counting with BP Linear Search, Combining BP Maximum Search with BP Picking, Combining BP Picking with BP Maximum Search, Combining BP, Picking with BP Copy

5. Sorting

Sorting with Simple Changes (SSC), Minimum Selection Sort (MSS), Bubble Sort (BS), Modified Bubble Sort, Insertion Sort (IS), Modified Insertion Sort (MIS), Shell Sort (SHS)

6. Searching

Linear Search in a sorted sequence, Binary Search, Application of Binary Search, applications of Binary Search: BP Decision, BP Selection, BP Picking and BP Counting for sorted sequences

7. Sets

Set as a data structure, creation of a set out of a sorted array; check whether an array is a set, membership, inclusion, subset, Union, intersection, subtraction, complement, symmetric difference

8. Recursion 1

Idea of recursion, general model, recursive function call, advantages and disadvantages. Program transformations: R ! I transformation, I ! R transformation, examples.

9. Recursion 2

Recursive conversion of a number to another base Recursive and iterative factorial, Recursive and iterative. Fibonacci algorithm, recursive binomial (bin, bin1, bin2), Hanoi towers, String reversal (reverse, reverse1), palindrome (palindrome, palindrome1, and palindrome2), power and power1

10. Advanced sorting 1

Recursive Merge Sort, Recursive Quicksort. Description, performance, randomized version.

11. Advanced sorting 2

Heap, min-heap and max-heap, heap algorithms, heapsort.

12. Advanced sorting 3

Distribution sort, counting sort, radix sort, bucket sort.

13. Dynamic Programming

Greedy algorithms. Divide-and-Conquer strategy, the idea of Dynamic Programming, the knapsack-problem. Longest Common Subsequences. Matrix Chain Multiplication.

14. Backtracking

The idea of backtracking, the 8-queens problem

15. Lists

Definitions, comparison with the array, list algorithms (traversal, search, insert, delete).

16. Sorted linked lists. Definitions, algorithms (traversal, search, insert, delete), sentinel nodes, special linked lists (doubly, multiply, circular)

17. Graphs 1

Directed, undirected, weighted graphs, graph as data structure, path, connectivity, Cycles, Components. Finding an acyclic path (the labyrinth problem: Theseus, Ariadne and Minotaur).

18. Graphs 2

Minimum-weight spanning trees (Kruskal, Prim).

19. Graphs 3

Maximum flow.

20. Binary Search Tree

Concept of a tree, definitions, binary tree, binary search tree, BST operations (lookup, traversals, insert, remove)

21. B-trees

Definitions, advantages, disadvantages, insert a node, remove a node.

22. Hashing

The idea, direct addressing, various hashing tables, universal hashing, collision, solutions.

23. Object oriented programming

Inheritance, overriding, hiding, problems of multiple inheritance, polymorphism, non-virtual and virtual methods.

24. Interfaces

Implicit and explicit interfaces, sorting example

25. Event handling

Function pointers, events, delegates, examples.

26. Exception handling

Advantages, system exceptions, application exceptions, your own exceptions, exception rethrow, best practices, examples