Preamble :Algorithms are Core of computer science and software engineering. The real-world performance of any software system depends on only two things:
The algorithms chosen
The suitability and efficiency of the various layers of implementation.
The study of algorithms provides insight into the intrinsic nature of the problem as well as possible solution techniques, independent of programming language/ programming paradigm/computer hardware/ implementation aspect.
Selection of algorithms appropriate to particular purposes and applying them or recognizing the possibility that no suitable algorithm may exist is a challenging task . This relies on understanding the range of algorithm, recognizing their strengths and weaknesses, efficiency and their suitability in the target domain.
Due to availability of multi-core processors,parallel algorithms are also relevant now for increasing throughput. In the current semester we will put some light on approximation and randomized algorithm.
Overview of algorithms and their importance in computer science
Basic algorithmic concepts , notation
Analysis of algorithms and their complexity
5 Hr
Learning Outcome
Understand the importance of algorithms in computer science.
Identify basic algorithmic concepts and notation.
Analyze the complexity of algorithms using mathematical notation and techniques.
Overview of the divide-and-conquer strategy
Examples of divide-and-conquer algorithms: binary search, merge sort, quicksort, etc.
Analysis of divide-and-conquer algorithms and their complexity
5 Hr
Learning Outcome
Understand the divide-and-conquer strategy and its application in algorithm design.
Identify and implement divide-and-conquer algorithms such as binary search, merge sort, and quicksort.
Analyze the complexity of divide-and-conquer algorithms using mathematical notation and techniques.
Overview of the dynamic programming approach
Examples of dynamic programming algorithms: Fibonacci sequence, shortest path, knapsack problem, etc.
Analysis of dynamic programming algorithms and their complexity
6 Hr
Learning Outcome
Understand the dynamic programming approach and its application in algorithm design.
Identify and implement dynamic programming algorithms for problems such as the Fibonacci sequence, shortest path, and knapsack problem.
Analyze the complexity of dynamic programming algorithms using mathematical notation and techniques.
Overview of the Greedy strategy
Examples of greedy algorithms: Huffman coding, minimum spanning tree, etc.
Analysis of greedy algorithms and their complexity
6 Hr
Learning Outcome
Understand the greedy strategy and its application in algorithm design.
Identify and implement greedy algorithms such as Huffman coding and minimum spanning tree.
Analyze the complexity of greedy algorithms using mathematical notation and techniques.
Overview of graph algorithms and their applications
Examples of graph algorithms: depth-first search, breadth-first search, Dijkstra's algorithm, etc.
Analysis of graph algorithms and their complexity
6Hr
Learning Outcome
Understand the applications of graph algorithms in computer science and other fields.
Identify and implement graph algorithms such as depth-first search, breadth-first search, and Dijkstra's algorithm.
Analyze the complexity of graph algorithms using mathematical notation and techniques.
Introduction to NP-completeness and its importance in algorithm design
Examples of NP-complete problems: Boolean satisfiability, traveling salesman problem, etc.
Techniques for dealing with NP-complete problems: approximation algorithms, heuristics, etc.
6Hr
Learning Outcome
Understand the concept of NP-completeness and its importance in algorithm design.
Identify examples of NP-complete problems such as Boolean satisfiability and the traveling salesman problem.
Apply approximation algorithms and heuristics to deal with NP-complete problems.
Introduction to advanced topics in algorithm design: Randomized algorithms, parallel algorithms, Distributed and Decentralised Approaches etc.
Applications of advanced algorithms in areas such as machine learning, cryptography and Information Security and bioinformatics
6 Hr
Learning Outcome
Understand the concept of randomized algorithms and their applications in computer science.
Understand the concept of parallel algorithms and their applications in computer science.
Understand the applications of advanced algorithms in fields such as machine learning, cryptography, and bioinformatics.
"Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein.
"Algorithm Design" by Kleinberg and Tardos.
"The Design of Approximation Algorithms" by Williamson and Shmoys.
NPTEL lectures on "Design and Analysis of Algorithms" by Prof. S. Arun Kumar.
NPTEL lectures on "Advanced Algorithms" by Prof. Sundar Vishwanathan.
"Algorithms" by Jeff Erickson. This is a comprehensive online textbook that covers all the topics included in the syllabus.
"Algorithmic Thinking, Peak Finding" by Prof. Eric Grimson and Prof. John Guttag.
Topics-To be Covered
Definition of Algorithms, Criterion , Designing v/s Analysis issues, Basic problems and formulation of simple algorithms.
Asymptotic analysis of upper and average complexity bounds.
Identifying differences among best, average, and worst case behaviors.
Big- O, little o, omega, and theta notation.
Time and space trade-offs in algorithms.
Using recurrence relations to analyze recursive algorithms.
Brute-force algorithms.
Greedy algorithms.
Divide-and-conquer.
Backtracking.
Branch-and-bound.
Heuristics.
Pattern matching and string/text algorithms.
Sequential and binary search algorithms.
Quadratic sorting algorithms (selection, insertion).
O(N log N) sorting algorithms (Quicksort, heapsort, mergesort).
Hash tables, including collision-avoidance strategies, Dictionaries.
Binary search trees.
Representations of graphs (adjacency list, adjacency matrix).
Depth- and breadth-first traversals, Shortest-path algorithms.
Minimum spanning tree (Prim’s and Kruskal’s algorithms).
Tim Sort.
Definition of the classes P and NP.
NP-completeness (Cook’s theorem).
Standard NP-complete problems.
Reduction techniques
2023: First Internal Test Feb 2023
Previous years Questions
References and Suggested Redings:
Jon Kleinberg, Eva Tardos, “Algorithm Design”,Pearson Education India.
Thomas H. Cormen,Charles E.Leiserson,Ronald L. Rivest and Clifford Stein, “Introduction to Algorithms”-Second edition,PHI Publication
Aho, Hopcroft and Ullman,“The design and analysis of computer Algorithms”,Pearson Education.
Ellis Horowitz,Sartaj Sahni , S. Rajasekaran , “Fundamentals of computer algorithms”,Galgotia Publications
IGNOU Materials for “analysis and design of algorithms”
R.G. Dromey, "How to Solve it by computers", Pearson Education-2007
Donald Ervin Knuth,"The Art of Computer Programming: Fundamental algorithms",Addison-Wesley, 2008.
Internal Test-1 (MCA-IC-2K-10 , M.Tech-IT-2K-10)
(Solutions-video of the test-1 by prabhanshu of M.Tech. -Correctness is to be checked )
PG Project Idea: Designing , Development and implementation of automated tool for indexing of Video Assignment/ lectures/Tutorial/Paper Solution Discussion e-Library (Classification, Clustering and Association Mining from Video repository)
Video Assignments Submitted by Students of IIPS
(order is according to submission sequence)
Gaurav Parmar- Introduction to Algorithms and Bubble Sort
Shaifali Agrawal:
Late Submissions:
Prabhanshu Sharma-Cache Mapping
Shailendra singh Thakur:
Time Complexities of Fibonacci -Iterative & Recursive Time Complexities of Fibonacci -Iterative & Recursive approach.
Ashika Gupta-Merge Sort and it's Complexity analysis
Deepesh Parihar -Analysis of Binary Search
Santosh Uplawdiya-Merge Sort Algorithm
Harshdeep Bhalse-Tower of Hanoi
Rahu Patel -Combination Problem
Shailendra Katolkar-Insertion Sort,
Aastha Jaiswal-Insertion Sort[Submitted in May-2014]
Chetna Suryavanshi- Quick Sort
Prachi Pawar-LCS
Yamini Sarraf- Complexity of Linear and Binary Search
Divya Akole -Fibonacci Number and Golden Ratio
Submissions after Test-3 (22-March-2014)
Ashwini wadikar-Knapsack
Ruchi Rangari-Dijkstra Algorithm
Palak Chauhan-Kruskal's Algorithm
Bhasha Raghuwanshi-LCS
Srashti tawli - Line Algorithm
Submission in April-2014
Rahul Dawar- Data Structures(April-1, 2014)
Navneet Seth-Selection Sort (April-1, 2014)
Avesh Khan-Selection Sort
Ankit Singh Kushwah-LCS {Repated Topic, Already chosen by Prachi Pawar}
Renuka Dhakad greedy technique-Huffman Code and Knapsack problem (5/5/2014)
Palak Thirwan-Minimum Spanning Tree Prim's Algorithm (5/5/2014)
Apurva Jain-Sequence alignment problem and dynamic programming (5/5/2014)
Shiksha Jadhav-Quick Sort analysis (5/5/2014)