SYLLABUS

    Fundamentals
  1. Growth of Functions, Big-O,Omega and Theta Notations : 2.2
    Graphs
  2. Introduction and Terminology : 8.1 , 8.2
  3. Representing Graphs,Connectivity,Euler and Hamilton Paths : 8.3-8.5
  4. Shortest Path Problems:Dijkstra's Algorithm : 8.6
  5. Planar Graphs:Map Coloring : 8.7 , 8.8
    Trees
  6. Introduction and Applications:Binary Search Tree,Huffman Coding : 9.1 , 9.2
  7. Tree Traversal : 9.3
  8. Spanning Trees:Depth First Search/Backtracking,Breadth First Search : 9.4
  9. Minimum Spanning Trees:Prim and Kruskal's Algorithms : 9.5
    MIDTERM , Thursday 28th July
    Boolean Algebra
  10. Boolean Functions and their Representation : 10.1 , 10.2
  11. Logic Gates : 10.3
  12. Minimization of Circuits : 10.4 (skipped)
    Modeling Computation
  13. Languages and Grammars : 11.1
  14. Finite State Machines with/without output : 11.2 , 11.3
  15. Language Recognition : 11.4
  16. Turing Machines : 11.5
    FINAL , Thursday 18th August :
    Final is cummulative with emphasis on the material after the midterm. Primarily work on the assignment-midterm problems, then the class notes with related problems in the book. Good Luck. M.K.
ASSIGNMENTS
1 , 2 , 3 , 4


Back to main page