|
Algorithms, building blocks of algorithms (statements, state, control flow, functions), notation (pseudo code, flow chart, programming language), algorithmic problem solving, simple strategies for developing algorithms (iteration, recursion). Illustrative problems: find minimum in a list, insert a card in a list of sorted cards, guess an integer number in a range, Towers of Hanoi. |
Conditionals: Boolean values and operators, conditional (if), alternative (if-else), chained conditional (if-elif-else); Iteration: state, while, for, break, continue, pass; Fruitful functions: return values, parameters, local and global scope, function composition, recursion; Strings: string slices, immutability, string functions and methods, string module; Lists as arrays. Illustrative programs: square root, gcd, exponentiation, sum an array of numbers, linear search, binary search.
Lists: list operations, list slices, list methods, list loop, mutability, aliasing, cloning lists, list parameters; Tuples: tuple assignment, tuple as return value; Dictionaries: operations and methods; advanced list processing - list comprehension; Illustrative programs: selection sort, insertion sort, merge sort.
|
Text files, reading and writing files, format operator; command line arguments, errors and exceptions, handling exceptions, modules, packages; Illustrative programs: word count, copy file. |
- Teacher: Dr. Priyanka Gupta
Design and Analysis of Algorithms(CSE 216)
COURSE OUTCOMES
CO1: Understanding the correctness of algorithms using inductive proofs and invariants.
CO2: Describing worst-case running times of algorithms using asymptotic analysis.
CO3: Analyzing the divide-and-conquer paradigm and explain when an algorithmic design situation calls for it. Recite algorithms that employ this paradigm. Synthesize divide-and-conquer algorithms. Derive and solve recurrences describing the performance of divide-and-conquer algorithms.
CO4: Evaluating the dynamic-programming paradigm and explain when an algorithmic design situation calls for it. Recite algorithms that employ this paradigm. Synthesize dynamic-programming algorithms, and analyze them.
COURSE CONTENTS:
MODULE-I
Introduction: Algorithms, analyzing algorithms, Complexity of algorithms, Growth of functions, Performance measurements, Sorting and order Statistics - Shell sort, Quick sort, Merge sort, Heap sort, Comparison of sorting algorithms, Sorting in linear time.
MODULE-II
Advanced Data Structures: Red-Black trees, B – trees, Binomial Heaps and Fibonacci Heaps.
MODULE-III
Applications and Examples: Divide and Conquer examples such as Sorting, Convex hull . Greedy methods with examples Huffman Coding, Knapsack, Minimum Spanning trees – Prim’s and Kruskal’s algorithms, Single source shortest paths - Dijkstra’s and Bellman Ford algorithms.
MODULE-IV
Dynamic Programming: Dynamic programming with examples such as LCS, All pair shortest paths – Warshal’s and Floyd’s algorithms, Resource allocation problem. Backtracking, Branch and Bound with examples such as Travelling Salesman Problem, Graph Coloring, n-Queen Problem, Hamiltonian Cycles and Sum of subsets.
MODULE-V
Approximation and NP": Algebraic Computation, String Matching, Theory of NP-completeness, Approximation algorithms and Randomized algorithms.
TEXT BOOKS:
1. Thomas H. Coreman, Charles E. Leiserson and Ronald L. Rivest, “Introduction to Algorithms”, Printice Hall of India.
REFERENCE BOOKS:
1. RCTLee, SS Tseng, RC Chang and YT Tsai, “Introduction to the Design and Analysis of algorithms”, Mc Graw Hill.
2. E. Horowitz & S Sahni, "Fundamentals of Computer Algorithms".
3. Berman, Paul,” Algorithms”, Cengage Learning.
4. Aho, Hopcraft, Ullman, “The Design and Analysis of Computer Algorithms” Pearson Education.
- Teacher: SANJU BALA
Design and Analysis of Algorithms(CSE 216)
COURSE OUTCOMES
CO1: Understanding the correctness of algorithms using inductive proofs and invariants.
CO2: Describing worst-case running times of algorithms using asymptotic analysis.
CO3: Analyzing the divide-and-conquer paradigm and explain when an algorithmic design situation calls for it. Recite algorithms that employ this paradigm. Synthesize divide-and-conquer algorithms. Derive and solve recurrences describing the performance of divide-and-conquer algorithms.
CO4: Evaluating the dynamic-programming paradigm and explain when an algorithmic design situation calls for it. Recite algorithms that employ this paradigm. Synthesize dynamic-programming algorithms, and analyze them.
COURSE CONTENTS:
MODULE-I
Introduction: Algorithms, analyzing algorithms, Complexity of algorithms, Growth of functions, Performance measurements, Sorting and order Statistics - Shell sort, Quick sort, Merge sort, Heap sort, Comparison of sorting algorithms, Sorting in linear time.
MODULE-II
Advanced Data Structures: Red-Black trees, B – trees, Binomial Heaps and Fibonacci Heaps.
MODULE-III
Applications and Examples: Divide and Conquer examples such as Sorting, Convex hull . Greedy methods with examples Huffman Coding, Knapsack, Minimum Spanning trees – Prim’s and Kruskal’s algorithms, Single source shortest paths - Dijkstra’s and Bellman Ford algorithms.
MODULE-IV
Dynamic Programming: Dynamic programming with examples such as LCS, All pair shortest paths – Warshal’s and Floyd’s algorithms, Resource allocation problem. Backtracking, Branch and Bound with examples such as Travelling Salesman Problem, Graph Coloring, n-Queen Problem, Hamiltonian Cycles and Sum of subsets.
MODULE-V
Approximation and NP": Algebraic Computation, String Matching, Theory of NP-completeness, Approximation algorithms and Randomized algorithms.
TEXT BOOKS:
1. Thomas H. Coreman, Charles E. Leiserson and Ronald L. Rivest, “Introduction to Algorithms”, Printice Hall of India.
REFERENCE BOOKS:
1. RCTLee, SS Tseng, RC Chang and YT Tsai, “Introduction to the Design and Analysis of algorithms”, Mc Graw Hill.
2. E. Horowitz & S Sahni, "Fundamentals of Computer Algorithms".
3. Berman, Paul,” Algorithms”, Cengage Learning.
4. Aho, Hopcraft, Ullman, “The Design and Analysis of Computer Algorithms” Pearson Education.
- Teacher: SANJU BALA