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 flip-flops, 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, flow 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: 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. Linked 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: classes, 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, custom exceptions, exception rethrow,
examples.
