In this thread we discuss our progress reading “Introduction to Algorithms, Fourth Edition”. We gather every Saturday and Sunday at 12:00 (noon) UTC.
Reading goals for next Saturday: Chapter 3
I've extended the time we have to finish chapter 3 because I was pretty busy with work this week. Did you get through all of this week's content? Let us know if you think we are going too fast or too slowly.
Today's discussion questions: Name a loop invariant property which is not mentioned in the book, and prove that it is loop invariant. 2.1-4 Write pseudocode for linear search, which scans through the array from beginning to end, looking for x . Using a loop invariant, prove that your algorithm is correct. Make sure that your loop invariant fulfils the three necessary properties.
You will gain the most by doing the exercises and problems yourself! Spoilers are not enabled on this board, so please not post solutions for exercises or problems for sections: 3.1 and beyond
Notable changes from the third edition for this week’s content: None
> 2.1-4 Write pseudocode for linear search, which scans through the array from beginning to end, looking for x . Using a loop invariant, prove that your algorithm is correct. Make sure that your loop invariant fulfils the three necessary properties.
My solution:
for i=1 to n if A[i]=x return i return NIL
Loop invariant: At the beginning of every iteration, no element of the subarray A[1:i-1] (or if i=1, the empty array) is equal to x
Charles Fisher
jeeze this one has a new version too? AIMA got a new edition in the last year or two too (which I have still not gotten around to).
CLRS is too dry for me to read back-to-back, but I could manage it with AIMA.
Should I but the printed one? I use my iPad to read and solve the CLRS, but it seems everyone else is using a printed actual textbook.
Mason Thompson
I'm using a PDF copy for now, and I'm going to buy a Kindle in a few days when they're on sale for prime day. I personally wouldn't buy a paper copy, I'd only borrow it if my university had the fourth edition.
Lucas Barnes
this_book = "A Common Sense Guide to Data Structures and Algorithms"
I started reading $this_book, done with chapter 10, and solved many example problems in code. Don't have any experience with leetcode and I think I'm average at coding (so far) What other resources should I use before starting with leetcode? My classmates keep posting solutions to problems like width of a binary tree and all, I just can't understand them. I'm also struggling to pick my "main" language. I did most of my projects in C or JavaScript but they both seem a bad choice. I'm really confused. Is there a guide/resource you think can help me :(
