Algorithm, Analysis & Design

Preamble :Algorithms are Core of  computer science and software engineering. The real-world performance of any  software system depends on only two things:

1. The  algorithms chosen

2. 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.

 Semester Jan-May 2023

• Syllabus  

• Study Material (Covid -19 Class Material)

•  Test-1 

• Test-2 

• Test-3

• EndSem-23

•  Assignment Submission Link

Unit-1:Introduction to Algorithms:

• 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.

Unit-2: Divide and Conquer:

• 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.

Unit-3: Dynamic Programming:

• 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.

Unit-4: Greedy Algorithms:

• 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.

Unit-5: Graph Algorithms:

• 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.

Unit-6:  NP-Completeness:

• 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.

Unit-7: Advanced Topics:

• 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.

Recommended References:

1. "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein.

2. "Algorithm Design" by Kleinberg and Tardos.

3. "The Design of Approximation Algorithms" by Williamson and Shmoys.

Online Courses

1. NPTEL lectures on "Design and Analysis of Algorithms" by Prof. S. Arun Kumar.

2. NPTEL lectures on "Advanced Algorithms" by Prof. Sundar Vishwanathan.

3. "Algorithms" by Jeff Erickson. This is a comprehensive online textbook that covers all the topics included in the syllabus.

4. "Algorithmic Thinking, Peak Finding" by Prof. Eric Grimson and Prof. John Guttag.

Video Assignments Submitted by Students of IIPS

(order is according to submission sequence)

• Gaurav Parmar- Introduction to Algorithms and Bubble Sort

• Shaifali Agrawal:

1. Space Complexity-1 ,

2. Space Complexity-2

Late Submissions:

• Prabhanshu Sharma-Cache Mapping

• Shailendra singh Thakur:

1. Time Complexities of Fibonacci -Iterative & Recursive Time Complexities of Fibonacci -Iterative & Recursive approach. 

2. Questionns based on Master's Theorem

3. Prim's Algorithm and complexity

• 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)