Search This Blog

Wednesday, June 22, 2022

Math required and resources for Computer Science 1st year students

These are the Computer Science Math Classes required for most 1st year programs. 

Pi CakePi Cake - pie of pis

Images provided by DALLE AI Model

Just to dispel any notions, you can certainly become a good coder/programmer without needing these higher level of mathematics. But if you want to know what goes on under the hood and understand different algorithms, it is beneficial. 

If you are studying in a bootcamp, they probably won't focus on these unlike in an academic environment such as university or college. 

Generally, you can start off with precalculus and algebra and then move on at your own pace to get up to speed! 

I will be updating this post and adding another for upcoming years including Calculus 2 and Linear Algebra 2, Discrete Mathematics, Probability, etc.) But it is really important to have a strong base before expanding on your knowledge. Specifically, precalculus and trigonometry show up throughout your academic career. 

Precalculus (Prerequisite and review): 

Forty Days to Mastery of Precalculus

Paul's Notes

I strongly advise solving problems and working through them, in addition to watching the videos.

Make sure to focus on logarithm, polynomial, and exponential functions.  In addition, work on synthetic division and analytical geometry. Lastly, learn about sigma notation,  sequences/sums, and proof by induction. 

Download the formula sheet here

Set Theory:

(sometimes its a part of pre-calc)

This subject doesn't usually get covered in high school. It is a branch of math logic. If you took Digital Systems (CS Course), you might recall De'Morgan's law and Venn diagrams which happen to be used here as well! 

It's important to recall the symbols, some of them are used frequently in other fields of mathematics. Linear Algebra uses unions and intersections (for example). 

Trigonometry:

(sometimes its a part of pre-calc)

Make sure to cover the inverse functions as well such as arcsin, arctan, etc. in addition to their counterparts. In college, you will not be permitted to use a graphic calculator and you will not always have a unit circle around... try practicing your trig on a scientific calculator if possible. 

Khan Academy Section

Pauls Notes 

Download the formula sheet here (precalculus with the major trig identities)

Calculus 1:

You will be learning about limits, derivatives, and integrals. This course is strongly based on proofs (induction, contradiction, etc.) . 

This also expands upon trigonometry in some ways and introduces new trigonometric terms such as sinh. 

Paul's Notes

Khan Academy Section (mostly high school calculus)

Help with limits

Download the formula sheet here

Books:

  • Calculus Made Easy by Silvanus P. Thompson (focuses on derivatives a lot, less on limits)
  • Calculus by James Stewart 

Linear Algebra:

Matrix manipulations, lots of higher dimensional thinking, not proof based. I found this course more intuitive than Calculus. Linear dependence, vectors, matrices, determinants, etc. 

Videos:

My playlist

Kim Brehm's playlist (amazing)

Khan Academy Section (limited amount of content)

Other content:

Lecture Slides

Archived version of Paul's Notes (the original version has been taken offline)

Codecademy guide and course (has some practical/code connections)

Guide for solving linear equations and matrices

Books: 

  • Elementary Linear Algebra by Howard Anton 
  • Linear Algebra by Jim Hefferon

General Resources:

Refer to the textbook the course requires or recommends. If you cannot afford the book, occasionally they have pdf versions on the internet for free. 
In addition, you can look at these as well: https://openstax.org/subjects (Free peer-reviewed books). 

Kim Brehm has a whole bunch of useful math videos

Thank you for reading, please share the article and follow me on twitter for more resources and guides!

Monday, June 20, 2022

C LeetCode Problem and Solution - Check if an array contains duplicate elements

DALLE Image of an array
DALLE Image of an array

C LeetCode problem and solution - Check if an array contains duplicate elements

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct. I provide two possible solutions in C, one is brute force and O(N^2) while the second one is O(nlogn). 

Example 1:

Input: nums = [1,2,3,1]

Output: true


Example 2:

Input: nums = [1,2,3,4]

Output: false


Example 3:

Input: nums = [1,1,1,3,3,4,3,2,4,2]

Output: true


My solution is quite intuitive and it runs in O(N^2) time. The worst case is where there are no duplicates, as both loops will have to execute till the end. Best case is if there are duplicate entries in the beginning as the program will detect tat and return true without needing to traverse so far. 

bool containsDuplicate(int* nums, int numsSize){
    for(int i = 0; i < numsSize; i++){ //outer loop n
        for(int j = 0; j < i; j++){ //inner loop n 
            if(*(nums+j) == *(nums+i)){
                return true; //found match
            }
        }
    }
    return false; 
}


As it is brute force, we are better off with a different approach. Unsurprisingly, this will not run in LeetCode because it just takes too much time ;) 

One possible approach would be to start sorting the array, then check for duplicates as they would have to appear in consecutive order. QuickSort, is the sort I selected is included in the C library. Unfortunately, the efficiency isn't defined from the C standard, but we can assume it works similar to/ if not better than a standard quick sort. 

It should be somewhere around O(nlogn) in the best and average case, while the worst is unknown as we don't know where the partition is... It is certainly going to be better than O(N^2). Just a reminder about the worst case in a standard QuickSort Algorithm... If the pivot happens to be at the start or end and the array is sorted already in ascending or descending order. If you were to put the pivot on a more optimal place, this case won't happen. 

Lastly, our check would occur in O(n) time. 

#include <stdlib.h> //base library


int compare(const void * i1, const void * i2) //the quick sort requires a compare function
{
return *(const int *)i1 - *(const int *)i2;
}

bool containsDuplicate(int* nums, int numsSize){
    qsort(nums, numsSize,sizeof(nums[0]), compare); //run the quicksort, pass the size of the array, size of each element (size of int), and the compare function
    for(int i = 0; i < numsSize-1; ++i){ //don't exceed bounds of array
            if(*(nums+i) == *(nums+i+1)){ //check current with next element
                return true;
            }
    }
    return false; 
}

An alternative approach is to implement your own sorting algorithm, and then do a check for duplicate entries there. Or, you can use another data structure such as a Set or HashSet. 

Thank you for reading, please share the article and follow me on twitter for more resources and guides!
  

Sunday, June 19, 2022

Data and Programming Structures - Guide for studying and free resources

While studying Data Structures and Algorithms 1, I came upon many resources which helped me! Here are some of the ones I reference quite frequently. For asymptotic analysis, Calculus comes in handy with Limits and L'Hôpital's rule (using derivatives). In addition, the lecturer's often referred to the CLRS Algorithms Book, the acronym is each of the author's first letter of their last names... Overall the book is quite helpful, it is lacking details for the popular AVL Tree (self balancing binary search tree), but besides that it is great. 

I have added plenty of resources below, intentionally there is a mix of academic links in addition to general ones. Computer Science and Data Structures as a field tend to work on the more theoretical level, but I see value in the practical side of Data Structures and Algorithms as well which justifies my choice!

An example of this is using pseudo-code, it is general practice to use it in college and universities rather than a specific programming language. This is because it allows an idea to be conveyed without dealing with quirks of certain languages. A side effect of this is that the code cannot be compiled nor run, this can be good as if you made a mistake it is harder to dock you points. But at the same time, if you made a mistake it is harder to test and find it. 

DALLE Generated image of a BST
DALLE Generated image of a BST

Complexity:

I put a graph together on desmos which you can play with and see for yourself how a large enough N (or x in this case) can impact performance of algorithms. We can assume that X will never be <= 0, as it wouldn't be realistic or even practical to have a data structure with no elements. 

Academically we have 5 different symbols for asymptotic notation:
        o  O  Θ   Ω   ω
F(n) < <=   =   >=  >  G(n)

(in order of appearance) Often called: little O, big O, theta, Big omega, little omega

This strictly means, if F(n) is o(g(n)), then F(n) is certainly better than G(n). You can extend this to the rest of the symbols logically via the comparison symbols I placed. 

Heads up! In the workforce and hi-tech, they most often use Capital Omicron, or Big-oh (and occasionally theta and Capital Omega). 

These are essentially considered bounds of a function. We then can use this notation to compare two functions or an algorithm to some bound. Such as 3n+1 = O(N2), which directly translates to 3n+1 <= N2  which is in fact true. The general extension of asymptotic notation is to use it to determine the time and space complexity of an algorithm. As an example, Quick Sort takes the time complexity of Θ(n log n) for both the best and average case. But in the worst case, it takes Θ(N2). As a side note the worst case can be essentially avoided if the pivot element is decided randomly or logically based on the size of the array and positions of elements.

Courses:

https://www2.cs.sfu.ca/CourseCentral/225/jmanuch/lectures.html (Course for auditing)


 

https://www.cs.cmu.edu/~15110-f12/lectures.html (some content is related to DS)



https://www.youtube.com/watch?v=IgeJmTKQlKs&list=PLpPXw4zFa0uKKhaSz87IowJnOTzh9tiBk&index=2 (Rob Edwards YouTube Playlist - San Diego State University) - Amazing videos! 

Additional resources/Guides:

https://algs4.cs.princeton.edu/cheatsheet/ (very conclusive and helpful)

https://www.bigocheatsheet.com/ (basic overview)

https://www.algorithm-archive.org (Limited amount of content)



Books:

Algorithms by Jeff Erickson (Freely distributed by the author)


CLRS Solutions (3rd party solutions to the practice questions in the book):


https://walkccc.me/CLRS/Chap01/1.1/  

https://sites.math.rutgers.edu/~ajl213/CLRS/CLRS.html


Code implementations:

https://github.com/luiseduardo1/Cormen-Algorithms-Data-Structures (in C)



Algorithms visualized:

Amazing ones:

https://visualgo.net/en (their BST implementation doesn't handle duplicates)

https://www.cs.usfca.edu/~galles/visualization/Algorithms.html  (Many different options and animations)


https://sortvisualizer.com/  (This one is OK)



Thank you for reading, please share the article and follow me on twitter for more resources and guides!