# UG Core Courses

Course No: CS141

Prerequisites: None

Credit: 2

Classes per week: 3 Hours Lab + 1 Lecture

Syllabus: - Module 0: Introduction to Computers, Notion of Algorithm, Linux Bash Shell, Simple Shell Programs.
- Module 1: Introduction to Programming: Variables, operators and expressions, input and output statements, Conditions and loops. Functions and recursions.
- Module 2: Arrays, Pointers, Structures, Classes and Objects. Module 3 (9P+3L): File i/o, command line arguments.
- Module 4: Abstract data type. Linked lists.

Reference Books: - B. W. Kernighan, D. M. Ritchie, The C Programming Language, Prentice-Hall, 2009.
- B. Stroustrup, The C++ Programming Language, Pearson, 2014.
- H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, MIT Press, Cambridge, 2009.
- D. Knuth: The Art of Computer Programming. Vol. 1, 2nd ed. Narosa/Addison-Wesley, New Delhi/London, 1973

Course No: CS142

Prerequisites: CS141

Credit: 2

Classes per week: 3 Hours Lab + 1 Lecture

Syllabus: - Module 0: Review of programming, Arrays and Linked List. Bubble Sort and Quick Sort. Binary Search.
- Module 1: Circular Linked Lists, Doubly Linked Lists, Stacks, Queues.
- Module 2: Trees. Binary Search Trees, Tree traversal, Balanced Binary trees.
- Module 3: Heap, Priority Queues.
- Module 4: Strings and Searching for Phrases.
- Module 6: (Optional) Dictionaries: universal, k-wise independent, simple tabulation hashing; chaining, dynamic perfect hashing, linear probing, cuckoo hashing

Reference Books: - B. W. Kernighan, D. M. Ritchie, The C Programming Language, Prentice-Hall, 2009.
- B. Stroustrup, The C++ Programming Language, Pearson, 2014.
- H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, MIT Press, Cambridge, 2009.
- D. Knuth: The Art of Computer Programming. Vol. 1, 2nd ed. Narosa/Addison-Wesley, New Delhi/London, 1973
- E. Horowitz,S . Sahni, Fundamentals of Data Structures in C++, Universities Press, 2008.

Course No: CS201

Prerequisites: None

Credit: 4

Classes per week: 3 Lectures + 1 Tutorial

Syllabus: - Module 1: Introduction to Finite State Automata; DFA,NFA, and their equivalence, Regular Ex- pressions and equivalence with finite state automata.Regular Languages and Properties, Pumping Lemma and applications, Myhill-Nerode Theorem, State Minimization.
- Module 2: Context Free Languages (CFL) and grammars, parse trees, Chomsky Normal Form. Pushdown Automata (PDA), Equivalence of acceptance by final state and empty stack. Equivalence of CFL and PDA, Pumping Lemma for CFL.
- Module 3: Turing Machines and equivalence of different models. Universality. Decidability, Recog- nizability, Enumeration, and Undecidability. Reductions. Rice’s Theorem, recursion theorem.
- Module 4: Notions of P,NP,co-NP, hierarchy theorem, NP completeness, Cook-Levin Theorem, NP completeness proofs of some NP complete problems.

Reference Books: - J. Hopcroft, JD Ulman. Introduction to Automata Theory, Languages and Computations. Narosa Publishing 2002. (Indian Edition)
- M. Sipser. Introduction to the Theory of Computation. Cengage, 3rd Edition, 2014.
- H. R. Lewis and C. H. Papadimitriou: Elements of The Theory of Computation, Prentice Hall, Englewood Cliffs, 1981
- M. R. Garey and D. S. Johnson: Computers and Intractability: A Guide to The Theory of NP Completeness, Freeman, New York, 1979.

Course No: CS202

Prerequisites: none

Credit: 4

Classes per week: 3 Lectures + 1 Tutorial

Syllabus: - Module 1: Review of Sets, Operations, Principles of Inclusion and Exclusion. Functions, relations, Equivalence relations. Countable and uncountable sets. Review of Pigeonhole principle.
- Module 2: Introduction to Propositional Logic, Equivalence and Implications. Truth tables, De Mor- gan’s Law, Quantifiers, Inference and Proofs. Introduction to First Order Logic, Syntax and Semantics, Soundeness and Completeness.
- Module 3: Mathematical Induction, Recursions, First order linear recurrence, Geometric series, Re- cursion trees and growth rates of solutions to recurrences, Master Theorem. Generating Functions.
- Module 4: Introduction to counting, sum and product principles, counting subsets. Binomial coeffi- cients and Pascal’s triangles. Polya’s theory of counting (optional).
- Module 5: Arithmetic Algorithms: Computing GCD, primality testing, RSA.
- Module 6: Graph Theory: Graphs, representations, connectivity, cycles, trees, Spanning tree of a graph, Algorithms to find minimum spanning trees. Eulerian Cycle and Hamiltonian paths, independence number and clique number, chromatic number, Dominating Sets, and Covering Sets. Planar Graphs. Directed Graphs and tournaments.
- Module 7: Probabilistic tools, Tail Bounds and Applications.
- Module 8: (Optional) Linear Algebraic tools in Combinatorics.

Reference Books: - J. Gallier, Logic for Computer Science: Foundations of Automatic Theorem Proving, Wiley.
- Kenneth Rosen. Discrete Mathematics and Its Applications, 7th Edition , McGraw Hill Publishing Co., 2012.
- Ken Bogart. Discrete Mathematics for Computer Science. available at https://www.kth.se/social/files/557ec6b0f276547
- J. L. Mott, A. Kandel and T. P. Baker: Discrete Mathematics for Computer Scientists, Reston, Virginia, 1983
- J. A. Bondy and U. S. R. Murty: Graph Theory with Applications, Macmillan Press, London, 1976.
- F. S. Roberts: Applied Combinatorics, Prentice Hall, Englewood Cliffs, NJ, 1984

Course No: CS301

Prerequisites: CS202

Credit: 4

Classes per week: 3 Lectures + 1 Tutorial

Syllabus: - Module 1: Introduction and basic concepts - mathematics of algorithm analysis, asymptotic notations, worst case and average case complexity. Review of Searching and Union Find.
- Module 2: Divide and conquer- Motivating algorithms that leads into recurrences, solving recurrences, merge sort and its recurrence, Median computation. Analysis of quicksort.
- Module 3: Greedy algorithms- Greedy choice, optimal structure property, minimum spanning tree, knapsack
- Module 4: Dynamic programming- Integral knapsack, longest increasing subsequence, edit distance, independent sets in trees
- Module 5: Graph algorithms- Recall of representation of graphs, BFS, DFS, shortest path, connected components, topological sort of DAGs, biconnected components and strongly connected components in directed graphs
- Module 6: (Optional) Randomization- Median, randomized quicksort, probabilistic primality testing. Algebraic Algorithms. Karatsuba’s algorithm and the Fast Fourier transform

Reference Books: - H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, MIT Press, Cambridge, 2009.
- S. Dasgupta, C. Papadimitrou, U. Vazirani, Algorithms, McGraw-Hill Education, 2006.
- A. Levitin, Introduction to Design and Analysis of Algorithms, Pearson 2007 (Lev)
- J. Kleinberg and E. Tardos, Algorithm Design, Pearson, 2005 (KT)
- E. Horowitz, S. Sahni, and S. Rajasekaran, Computer Algorithms, Silicon Press, 2007
- M. Goodrich, R. Tamassia, Algorithm Design, Wiley, 2001.
- D. Knuth: The Art of Computer Programming. Vol. 1 and Vol 3. , 2nd ed. Narosa/Addison-Wesley, New Delhi/London, 1973

Corporate Site - This is a contributing Drupal Theme

Design by

WeebPal.