Design and Analysis of Algorithm

Description:

In this module, we will enhance your logical and computational thinking.

Learning Objectives:

Students will understand

Objective 1: Understands and applies knowledge of abstraction, pattern recognition, problem decomposition, number base conversion, and algorithm formats

Objective 2: Understands and applies knowledge of algorithm analysis, searching and sorting algorithms, recursive algorithms, and randomization

Ethics: You should never attempt to penetrate that system or adversely affect that system’s operation. Such actions are a violation of KSU policy and, in some cases, violations of State and Federal law. Likewise, you should refrain from writing computer viruses, worms, self-reproducing code, or other kinds of potentially damaging software for this course unless you have explicit, written approval for the specific type of software that you wish to create. These kinds of programs are notoriously difficult to control and their release (intentional or otherwise) can result in substantial civil and criminal penalties. Please read and review the ACM Code of Ethics and Professional Conduct.

Mapping to Learning Objectives in K-12 CS Standards or GACE CS Assessment: Algorithms and Computational Thinking (25% in GACE CS)

Targeting CS Teacher Education Courses: CS Principle, AP Computer Science

Activities:

• Pre-Lab Activities

  1. JavaScript Tutorial

  2. Introduction to Javascript on Khan Academy

  3. Debugging JavaScript - Chrome DevTools 101

• Lab Activities

  1. Introduction to Algorithms

  2. A Guessing Game

  3. Binary Search

     • Implementing binary search of an array

     • Challenge: binary search

     • Run time analysis

     • Quiz

  4. Program Efficiency

     • Understand program efficiency part 1 and part 2 from MIT

     • Asymptotic notation

     • Big-\Theta

     • Functions in asymptotic notation

     • Quiz

     • Big-O

     • Big-\Omega

     • Quiz

  5. Sorting

     • Swap

     • Selection sort

     • Find minimum

     • Implement selection sort

     • Time analysis for selection sort

  6. Insertion sort

     • Implement insert

     • Pseudo code

     • Implement insertion sort

     • Time analysis for insertion sort

  7. Recursion

     • Factorial function

     • Iterative factorial

     • Recursive factorial

     • Write a recursive factorial function

     • Properties of recursive algorithms

     • Using recursion to determine whether a word is a palindrome

     • Is a string a palindrome?

     • Computing powers of a number

     • Recursive powers

     • Improving efficiency of recursive functions

  8. Number Base Conversion

     • Binary

     • Octal

     • Decimal

     • Hexadecimal

• Post-Lab Activities

  1. List what you have learned

  2. List what else you want to learn and where to find the resources (detailed with links)

• Review GACE CS questions and answers

• Assignments

  1. Design pseudo code to read a CSV file containing a sorted list of numbers and search a given number using binary search. Implement it using Javascript.

  2. Design pseudo code for reading a CSV file with numbers and sort them using selection sort. Implement your pseudo using Javascript.

  3. Design pseudo code for reading a CSV file with numbers and sort them using insertion sort. Implement your pseudo using Javascript.

  4. Design pseudo code for computing Fibonacci numbers using recursion and implement the code using Javascript.

• Project

  1. Work with your partner (two students in a project)

  2. Start from here to come up with your project