Algorithms Design & Analysis Lab (Spring 2022)

Section outline

• Select section CSE214 & CSE215 (Theory & LAB)

  CSE214 & CSE215 (Theory & LAB)

  Go to section CSE214 & CSE215 (Theory & LAB)

  "For me, great algorithms are the poetry of computation"

                                                                                                                                                                      --Francis Sullivan

  • Select activity Announcements

    

    Announcements Forum
  • Select activity Algorithm Online Class

    

    Algorithm Online Class URL

    Completion

    Students must

    

    Mark as done

    PC-A: 10:00 - 11:30 (Saturday), 08:30 - 10:00 (Monday), Lab 08:30 - 11:30 (Wednesday)

    PC-B: 13:00 - 14:30 (Saturday)  08:30 - 10:00 (Sunday) Lab 10:00 - 13:00 (Tuesday)

    
    

  • Select activity Counseling Hour

    

    Counseling Hour URL

    Completion

    Students must

    

    Mark as done
  • Select activity Instructor           &nb...

    Instructor

                 

    
    

    
    

    
    

    
    

    
    

             Dr. S M Aminul Haque 
    

             (Associate Professor)
    aminul.cse@daffodilvarsity.edu.bd 
    

          Telegram: 01847140129

    Prefects

       
    

          Md. Fazley Rabbe                 Md. Sharif Khan          Md. Shohidul Islam Polash        Shazzad Hossen
          Algorithm Prefect                Algorithm Prefect               Algorithm Prefect               Algorithm Prefect
          fazley15-1519@diu.edu.bd                sharif15-2002@diu.edu.bd            shohidul15-2523@diu.edu.bd         shazzad15-2420@diu.edu.bd
    

            Telegram: 01701046745                    Telegram: 01741976078                     Telegram: 01316400647                  Telegram: 01645288850

  • Select activity Quick Navigation ...

    Completion

    Students must

    

    Mark as done

    Quick Navigation

    Assessments: CT1  CT2  CT3      Assignment       Presentation         Mid Exam       Final Exam  Lab Test-1   Lab Test-2   Lab Final
    Week2Go:   WK1    WK2    WK3    WK4    WK5    WK6   WK7    WK8

• Select section Week 1: Ice Breaking and Course Overview

  Week 1: Ice Breaking and Course Overview

  Go to section Week 1: Ice Breaking and Course Overview

  Welcome Note from Instructor

  ABOUT COURSE

  GENERAL GUIDELINES ABOUT THE COURSE

  • All the students registered for this course have to enroll in the Blended Learning Center (BLC)
    
  • Students can find all the course materials in the BLC
    
  • Discussion forums are created to help students discuss about problems with their fellow classmates
    
  • Courses in the BLC is designed to promote active learning. So students must attach to BLC to progress their learning and to obtain good grades
    
  • Courses in BLC are designed to allow students to work both in onsite & offsite environment. Onsite/ online engagement will allow students to have interactions, group studies, and problem solving
    
  • Assessments are also designed in the BLC to ensure students are acquiring the desired skills from the course
    
  • In order to have quick communication between the instructor & the students, an instant messaging group is created using "Telegram" application
    

  COURSE RATIONALE

  Algorithms deals with efficient ways to solve different mathematical and real-life problems. It covers the common algorithms, algorithmic paradigms, and data structures used to solve computational problems. This course emphasizes the relationship between algorithms and programming and explores algorithms from the programmer’s perspective for solving problems efficiently using various programming languages.

  COURSE OBJECTIVES

  This course introduces students to the analysis and design of computer algorithms. Upon completion of this course, students will be able to do the following:

  • To analyze the asymptotic performance of algorithms
    
  • To demonstrate a familiarity with major algorithms and data structures
    
  • To apply algorithmic design paradigms like: divide & conquer, greedy, dynamic programming, graphs and methods of analysis of real life problems
    
  • To synthesize efficient algorithms in common engineering design situations
    

  COURSE TOPICS (WEEK-WISE)

  • Week01: Ice-breaking with students, Course Overview & Motivation
    
  • Week02: Function, Recursion, GCD, Introduction to Asymptotic notation and complexity analysis
    
  • Week03: Brute Force type problems: Linear Search, Insertion Sort, Bubble Sort, Selection Sort
    
  • Week04: Divide & Conquer: Binary Search, Quick Sort, Merge Sort
    
  • Week05: Greedy Algorithms: Coin Change, Bin Packing, Fractional Knapsack, Huffman Coding
    
  • Week06: Dynamic Programming: Fibonacci Series, DP Coin Change, 0/1 Knapsack
    
  • Week07: Midterm Examination: Week01 to Week06
    
  • Week08: Dynamic Programming: LCS, LIS
    
  • Week09: Introduction to Graphs, Graphs representation, BFS, DFS
    
  • Week10: Cycle Finding, Component Finding, SCC
    
  • Week11: Single Source Shortest Path Algorithms: Dijkstra's algorithm, MST
    
  • Week12: All Pair Shortest Path Algorithms: Bellmanford, Warshall
    
  • Week13: Presentation
    
  • Week14: Final Examination
    

  PREREQUISITE TOPICS

  • Programming: loops, arrays, functions, recursions, objects
    
  • Data structures: arrays, stacks, queues, link lists
    
  • Mathematics: high school algebra
    
  • Programming environment: CodeBlocks/ Eclipse
    

  REFERENCE MATERIALS

  • www.visualgo.net
    
  • www.geeksforgeeks.org
    
  • www.topcoder.com
    
  • www.codeforces.com
    
  • C Compiler for Android
    
  • C Compiler for ios
    

  FOR STUDENT SUPPORT

  • Student Portal: http://studentportal.diu.edu.bd/
    
  • Academic Guidelines: https://daffodilvarsity.edu.bd/article/academic-guidelines
    
  • Rules and Regulations of DIU: https://daffodilvarsity.edu.bd/article/rules-and-regulation
    
  • Career Development Center: https://cdc.daffodilvarsity.edu.bd/
    

  Student Interest Survey

  Activities: 6
• Select section Week 2: Introduction to Algorithm

  Week 2: Introduction to Algorithm

  Go to section Week 2: Introduction to Algorithm

  LESSON OBJECTIVE

  • To appreciate the role of algorithm in problem solving and importance of complexity analysis for algorithms
    

  LEARNING OUTCOMES

  • Interpret a problem
    
  • Appreciate & write an algorithm for the problem
    
  • Understand the importance of algorithm in solving real life problems
    
  • Identify the states of different complexity cases of an algorithm
    
  • Perform exercises on functions, recursions & pointers
    

  TOPICS

  • Algorithm definition
  • Introducing some real life problems
  • Introducing different algorithm strategies
  • Asymptotic Notation
  • Functions, Recursions, Pointers, Euclid's GCD algorithm (LAB)

  CONTENTS

  Activities: 10
• Select section Week 3: Brute Force: Searching & Sorting

  Week 3: Brute Force: Searching & Sorting

  Go to section Week 3: Brute Force: Searching & Sorting

  LESSON OBJECTIVE

  • To introduce with brute force type problems in searching & sorting domains
    

  LEARNING OUTCOMES

  • Knowledge about the Linear Search algorithm and its complexity
    
  • Knowledge about the Insertion sort algorithm and its complexity
    
  • Knowledge about the Bubble sort algorithm and its complexity
    
  • Knowledge about the Selection sort algorithm and its complexity
    
  • Exercise the Sorting and searching Algorithm with some additional problems
    

  TOPICS

  • Introduction to brute force techniques
  • Introduction to the searching Algorithm
  • ntroduction to the sorting Algorithm

  CONTENTS

  Activities: 10
• Select section Week 4: Divide & Conquer

  Week 4: Divide & Conquer

  Go to section Week 4: Divide & Conquer

  LESSON OBJECTIVE

  • To teach the main strategy of divide & conquer and the examples/ problems those are typically solved by this strategy and the complexity analysis of those problems
    

  LEARNING OUTCOMES

  • Explain how divide & conquer strategy works
    
  • Give examples of problems those are typically solved using divide & conquer strategy
    
  • Explain the complexity of the problems those are typically solved using divide & conquer strategy
    
  • Draw difference in complexity between brute force and divide & conquer
    

  TOPICS

  • Basic understanding of divide & conquer
  • Binary search & its complexity
  • Merge sort and its complexity analysis
  • Quick sort and its complexity analysis

  CONTENTS

  Activities: 10
• Select section Class Test 01

  Class Test 01

  Go to section Class Test 01

  Date/ Time: 15 October, 08:15 pm [Ensure your laptop/ phone is fully charged before attempting to the test]
  Syllabus: Week 01 to Week 04 (Introduction, Complexity, BF, D&C)

  Question Type: Open Book

  Open Book Test Guidelines

  During this open book test, you need to ensure the following items and code of conducts: 

  (1) Books, online repository and other relevant materials 
  (2) Your other supporting materials like clock, pen, pencil, eraser, calculator etc.
  (3) Drink water and have snacks 
  (4) No discussion in group or with your classmates as it will be reflected in your answers 
  (5) No sharing of codes, write-ups or ideas as this will be automatically detected by DIU BLC Plagiarism checker and will lead to negative marking 
  

  Total Test Time: 
  

  90 mins (15 mins for downloading the question paper & Answer script + 60 mins for answering the questions + 15 mins for submitting/ uploading the answers to BLC). Penalty will be incurred if failed to upload within the given time.

  During the Test: 
  

  (1) Download the question paper (pdf) from this section of DIU BLC 
  

  (2) You may type your answers directly on the provided space in BLC or you may type it in a doc file on your computer and copy & paste the answers in the assigned space provided in the BLC. Final submission must be through the assigned space provided in the BLC. No hand written text/ scan file will be granted.
  

  (3) You must mention corresponding Question number to the answers before you submit
  

  Activities: 0
• Select section Lab Test-1 (25%)

  Lab Test-1 (25%)

  Go to section Lab Test-1 (25%)

  Date/ Time: 20 October, 08:15 pm [Ensure your laptop/ phone is fully charged before attempting to the test]
  Syllabus: Week 02 to Week 04 (Brute force, D&C, Adhoc)

  Total Time: 
  

  120 mins.

  Total Marks: 
  

  3*15 (=45)
  

  Some Guidelines
  

  During this online lab test, you need to ensure the following items and code of conducts: 

  (1) Books, online repository and other relevant materials 
  (2) Your other supporting materials like clock, pen, pencil, eraser, calculator etc.
  (3) Drink water and have snacks 
  (4) No discussion in group or with your classmates as it will be reflected in your answers 
  (5) No sharing of codes, write-ups or ideas as this will be automatically detected by DIU BLC Plagiarism checker and will lead to negative marking
  

  Activities: 0
• Select section Week 5: Greedy Algorithm

  Week 5: Greedy Algorithm

  Go to section Week 5: Greedy Algorithm

  LESSON OBJECTIVE

  • To teach the basic methodology of greedy algorithm and the examples/ problems those are typically solved by this methodology and the complexity analysis of those problems
    

  LEARNING OUTCOMES

  • Appreciate the importance of solving certain problems using greedy algorithm strategy
    
  • Explain scenarios where greedy algorithm fails and need other strategies to solve
    
  • Solve the Coin Change Problem based on Greedy Method
  • Solve the Knapsack Problem based on Greedy Method
    
  • Solve the Huffman coding based on Greedy Method
    
  • Solve the  Bin packing Problem based on Greedy Method
    
  • Exercise the Sorting Algorithm with some additional problems in the Lab
    

  TOPICS

  • Properties of greedy algorithm
  • Coin change problem
  • Discussion on Bin packing Problem
  • Discussion on Knapsack Problem
  • Discussion on Huffman coding
    

  CONTENTS

  Activities: 10
• Select section Class Test 02

  Class Test 02

  Go to section Class Test 02

  Date/ Time: 2 Dec, 08:00pm [Ensure your laptop/ phone is fully charged before attempting to the test]
  Syllabus: Dynamic Programming

  Question Type: Open Book

  Open Book Test Guidelines

  During this open book test, you need to ensure the following items and code of conducts: 

  (1) Books, online repository and other relevant materials 
  (2) Your other supporting materials like clock, pen, pencil, eraser, calculator etc 
  (3) Drink water and have snacks 
  (4) No discussion in group or with your classmates as it will be reflected in your answers 
  (5) No sharing of codes, write-ups or ideas as this will be automatically detected by DIU BLC during evaluation and will lead to negative marking proposed by the system 
  

  (6) No copy text or code or any from Internet as this will be detected by DIU BLC system plagiarism checker during evaluation and this will lead to negative marking by the system

  Total Test Time: 

  90 mins (15 mins for downloading the question paper & Answer script + 60 mins for answering the questions + 15 mins for submitting/ uploading the answers in pdf format). Penalty will be incurred if failed to upload within the given time.
  

  Activities: 2
• Select section Midterm Examination

  Midterm Examination

  Go to section Midterm Examination

  
  

  Midterm Exam Topics:

  - Introduction to Algorithms
  - Complexity analysis,
  - Brute force
  - Divide & conquer
  

  - Greedy algorithm

  Midterm Exam Guidelines (click to view)
  

  Activities: 3
• Select section Week 6: Dynamic programming (part 1)

  Week 6: Dynamic programming (part 1)

  Go to section Week 6: Dynamic programming (part 1)

  LESSON OBJECTIVE

  • To teach the strategy of dynamic programming and the examples/ problems those are typically solved by this strategy and the complexity analysis of those problems
    

  LEARNING OUTCOMES

  • Explain the basic working procedure of dynamic programming
    
  • Give examples of problems those are typically solved using dynamic programming
    
  • Explain the complexity of dynamic programming

  TOPICS

  • Basic understanding of dynamic programming
  • Fibonacci series
  • 0/1 Knapsack problem
  • DP coin change problem

  CONTENTS

  Activities: 10
• Select section Week 7: Dynamic Programming (part 2)

  Week 7: Dynamic Programming (part 2)

  Go to section Week 7: Dynamic Programming (part 2)

  LESSON OBJECTIVE

  • To teach the strategy of dynamic programming and the examples/ problems those are typically solved by this strategy and the complexity analysis of those problems
    

  LEARNING OUTCOMES

  • Explain the basic working procedure of dynamic programming
    
  • Give examples of problems those are typically solved using dynamic programming
    
  • Explain the complexity of dynamic programming

  TOPICS

  • LIS (Longest Increasing Subsequence)
  • LCS (Longest Common Subsequence)

  CONTENTS

  Activities: 10
• Select section Week 8: Graphs (part 1)

  Week 8: Graphs (part 1)

  Go to section Week 8: Graphs (part 1)

  LESSON OBJECTIVE

  • To teach how graphs and trees play an important role in solving many of our real life problems and writing corresponding algorithms to solve the problems
    

  LEARNING OUTCOMES

  • Explain non-linear data structures (graphs & trees) and scenarios where they are used
    
  • Search over a graph or tree and make different operations on that
    
  • Interpret complexities of different graph operations

  TOPICS

  • Basics of graphs
  • Definitions of different types of graphs
  • Memory representation of graphs
    
  • Applications of graphs
    
  • Graph traversals (BFS, DFS)
    

  CONTENTS

  Activities: 8
• Select section Lab Final

  Lab Final

  Go to section Lab Final

  Date/ Time: 14 December, 06:00pm [Ensure your laptop/ phone is fully charged before attempting to the test]
  Syllabus: ALL that covered in the lab

  Total Time: 
  

  120 mins + 30 mins for VPL access issue

  Total Marks: 
  

  40
  

  Some Guidelines
  

  During this online lab test, you need to ensure the following items and code of conducts: 

  (1) Books, online repository and other relevant materials 
  (2) Your other supporting materials like clock, pen, pencil, eraser, calculator etc.
  (3) Drink water and have snacks 
  (4) No discussion in group or with your classmates as it will be reflected in your answers 
  (5) No sharing of codes, write-ups or ideas as this will be automatically detected by DIU BLC Plagiarism checker and will lead to negative marking

  Activities: 0
• Select section Class Test 03

  Class Test 03

  Not available

  Go to section Class Test 03

  Activities: 0
• Select section Week 10: Assignment

  Week 10: Assignment

  Go to section Week 10: Assignment

  Instructions:

  • Your Assignment will be taken as viva
  • It will be based on your basic understanding and short questions will be asked
  • Some samples of short questions are given in the "Course Introduction" section
  • Syllabus will be given in the class

  Activities: 0
• Select section Week 11: Presentation

  Week 11: Presentation

  Go to section Week 11: Presentation

  Presentation Mode & Topics:

  • Presentation will be individual and recorded
  • Find your topics here (pc-a, pc-b)

  General Instructions for the Presentation:

  • In presentation, marks will be given on: getup & outfit, body language, English command, eye contact, content knowledge, Q/A
  • Try to prepare the slides with more figures and less text. The font size of text should be larger so that it can be seen from the back bench of your class (if your are presenting through online due to COVID-19 pandemic, you are advised to ignore slides, instead prepare recorded presentation as per guidelines given to the link below)
  • Give slide number (during pandemic, you are advised to ignore slides)
  • More instructions will be discussed in the class

  A few Examples from previous good Presentations

  Activities: 1
• Select section Week 13: Final Examination

  Week 13: Final Examination

  Go to section Week 13: Final Examination

  
  

  24 December 2020 (9.00am to 1.00pm)

  Final Examination Topics:

  - Midterm Syllabus
  - Dynamic Programming
  

  - Graphs

  Online Exam Guidelines (click to view)
  

  Activities: 3
• Select section Lab Test 02 (25%)

  Lab Test 02 (25%)

  Go to section Lab Test 02 (25%)

  Date/ Time: 5 December, 07:00pm [Ensure your laptop/ phone is fully charged before attempting to the test]
  Syllabus: Brute force, D&C, Greedy, DP, Adhoc

  Total Time: 
  

  90 mins.

  Total Marks: 
  

  2*15 (=30)
  

  Some Guidelines
  

  During this online lab test, you need to ensure the following items and code of conducts: 

  (1) Books, online repository and other relevant materials 
  (2) Your other supporting materials like clock, pen, pencil, eraser, calculator etc.
  (3) Drink water and have snacks 
  (4) No discussion in group or with your classmates as it will be reflected in your answers 
  (5) No sharing of codes, write-ups or ideas as this will be automatically detected by DIU BLC Plagiarism checker and will lead to negative marking
  

  Activities: 0