Cs50 Week 3 Lecture: my summary and explanation

This week’s lecture was not that lengthy, not like week 2 taking up to 2 hours, it focuses mainly on searching and sorting, which is an algorithm used for finding an element in an Array.

Not even that alone, these week comes with an interesting Pset where we are told to write code that helps user vote for their favorite person, thus printing the winner.

Cs50 week 3 Summary

Already mentioned, we focus on Searching, an algorithm used for finding an element in an array. for example, linear search, Binary Search, and some different other types of algorithms used for sorting elements in an array like Selection sort, Merge sort.

We also talk about Struct, Recursion with lovely examples.

Before I talk about things I learn let me define these two basic terms

  • Big (O) notation: which means on the order of, it simply means how fast a program is, how much time an algorithm takes to run, it is known as the upper bound of a program or worst case. While the
  • Big (Ω) Notation: the lower bound of the number of steps for an algorithm, we can also call it the Best case, the minimum steps required for an algorithm to perform a specific task example include Linear and binary search that have Ω(1)

Linear Search is an algorithm that is used to find an element from an array, the idea of the algorithm is to iterate across the array from left to right, searching for the specific element

Pseudocode explained:

  • Repeat, starting the first element
    • if the first element is what you are looking for (target), stop
    • Otherwise, move to the next element.
  • The Worst case scenario is O(n) while the Best-case scenario is Ω(1)

Binary Search: this is also an algorithm used to find an element in an array, unlike Linear search, we have to Divide our problem into two(left or right), then search through either space depending on what we are looking for. Since we are dividing it into two we need it to be sorted first.

Pseudocode used

  • Repeat until the (sub)array is size 0:
    • Calculate the middle point of the current (sub)array
    • if the target is at the middle, stop.
    • else if, if the target is less than what is at the middle, repeat, changing the end point to be just to the left of the middle
    • else if the target is greater than what is at the middle, repeat, changing the start point to be just to the right of the middle.
  • The worst case scenario is O(n log n) while best case is Ω(1)
  • for binary search to work we need to sort element in the array.

Sorting: is an algorithm that is used to put an element in an array in a certain order.

We have the:

: the idea of the algorithm is to move higher valued elements generally towards the right and lower value elements generally towards the left

Selection Sort: the idea of the algorithm is to find the smallest unsorted elements and add it to the end of the unsorted list

Insertion sort: the idea of the algorithm is to build your sorted array in place, shifting elements out of the way if necessary to make room as you go.

Merge sort: the idea of the algorithm is to sort smaller arrays and then combine those arrays together (merge them) in sorted order.

  • Merge sort leverage the use of recursion.

Recursion: the process of repeating items in a self-similar way, it is a program that allows you to call a function inside the same function. i.e (Function calling itself)

Every recursive function have

  • The base case, which when triggered will terminate the recursive process
  • The recursive case, which is where the recursion will actually occur

Conclusion

Week 3 have not that easy, it’s full of strange things like sorting algorithm, searching, recursion and others, I need to do further research to understand some techniques.

Thanks for reading…..

1 comment

  1. Thanks

Leave a Reply