Summary of Class - 01

[svm11]

Here is a summary of the class that took place on 12th June, 2013 and the references you will needing.

• What are Algorithms?

• The C Programming Language - Kernighan & Ritchie

• Introduction to Algorithms - 3rd Edition - CLRS

  • First 3 chapters were covered.

  • Do read the analysis and the pseudo code from the book.

  • Do the questions in between the text and at the end of the chapter.

• Linear Search

  • Wiki

  • C Code

  • Write linear search in recursive fashion.

• Binary Search

  • Wiki

  • Topcoder Article

  • C Code

  • Write binary search in recursive fashion.

  • Write binary search using the inbuilt function present in the library of the programming language of your choice.

  • Modify the binary search algorithm to return the -(1 + insertion point) in case the key is not found in the array.

    • Eg. A = {1, 2, 4, 6, 7, 9, 51}, key = 8

    • key 8 is not present in the array A and should be inserted after 7 and before 9 to maintain the sorted property of the array. 

    • Hence insertion point = 5

    • Return value = -(1 + insertion point) = -(1 + 5) = -6

  • Currently the binary search algorithm returns any index pos such that A[pos] = key given duplicates in array A.

    • Modify the binary search algorithm to return the lowest index pos in case multiple key values are present in array A.

      • Eg. A = {1, 2, 4, 4, 5, 6, 6, 7, 8, 8, 8, 9, 51}, key = 8

      • Return value = 8

    • Modify the binary search algorithm to return the highest index pos in case multiple key values are present in array A.

      • Eg. A = {1, 2, 4, 4, 5, 6, 6, 7, 8, 8, 8, 9, 51}, key = 8

      • Return value = 10

• Use Google to find more about

  • In-place sort

  • Comparison sort

  • Stable sort

  • Online/Offline 

• Insertion Sort

  • Wiki

• Selection Sort

  • Wiki

• Bubble Sort

  • Wiki

• Merge Sort

  • Wiki

  • C Code

  • Working Applet

  • Write merge sort in iterative fashion.

• Find out the sort library function in the programming language of your choice and find the algorithm used to implement it.

• Inversion Count

  • Problem Statement - SPOJ

  • C Code

Some online judges for competitive programming. 

• Codechef

• Codeforces

• Topcoder - How to set up Topcoder Arena

• Spoj

• Light Online Judge

• UVA

• ACM-ICPC Live Archive

• Timus

• USACO

• Hacker Rank

• Hacker Earth

• Google Code Jam

• Topcoder Open

• Facebook Hacker Cup

Other resources

• C books

• C++ books

• Java books

• Freely available programming books

• Sun Java tutorial

Websites worth mentioning

• https://www.udacity.com/

• https://www.coursera.org/

• http://stackexchange.com/sites

• http://oeis.org/

• http://ideone.com/

• http://www.wolframalpha.com/

• http://www.cplusplus.com/

• http://www.java2s.com/

• http://www.geeksforgeeks.org/

It came to my notice that USACO is down currently. Instead of that, you can go to Codechef and solve top 10 easy problems sorted by decreasing number of accepted submissions. Refer to FAQ in case you face problems. Take help from your friends in case you are stuck. 

**First years** You are advised to go through all the links. 

**Second years** You are advised to spend more time on GeeksForGeeks.

Before the next class revise/complete C language. 

Study about Arrays, Linked lists, Stacks, Queues.