Programming Pearls Col 5 – A Small (but very important)Matter of Programming

Col 5 is all about the Science and Art of Testing (rules and where, when and how to apply the rules).

-Define expected output

-Cover all cases

-C/C++ Compile-time assertions:

Further reading: https://www.embedded.com/electronics-blogs/programming-pointers/4025549/Catching-errors-early-with-compile-time-assertions

-When the algorithm is part of a big program, use scaffolding/automated testing/line-by-line debugger

-When the algorithm is stand-alone, print statements might be faster

-Be wary of bugs in different environments, experiment with them frequently to gain insights for fixing bugs

 

 

Advertisements

Programming Pearls Col 4 – Writing Correct Programs

This column uses a simple and almost trivial example of writing the code for a binary search algorithm. Even programmers who so confidently claim that they can write flawless code ended up writing buggy code, and it’s simply because humans are always prone to error and we need to accept that.

Two principles to verify an iterative(loop) control structure:
-Define the invariant precisely (conditions for loops)
-Maintain the invariant as we write each line of code – key to converting algorithm/pseudo code to code

How to do the second one:

  1. Initialization: invariant is true at first iteration
  2. Preservation: invariant remains true at end before next iteration
  3. Termination: set clear termination conditions

Tools Used:

  • Assertion statements to enunciate states of the program
  • Do this then that control
  • Choose from cases control

Here’s the iteration control structure discussed in this column, simplified:

Drawing.png

Reflection:

This column touched on one of the most important topics – testing and verification. I think it gave that further explanation needed of so many things that computer science students were taught in class to do when they test the programs they write but never prompted to think deeply about the reasons behind them.

You may know what assertions are for, but why use assertions instead of just print statements? You know logical proofs are good for exercising your mathematical senses but how can it be applied to programming? Why do we need to write the obvious preconditions and postconditions for every class method? Why do we want to be able to explain every single line of code, besides just for the sake of being able to explain every single line of code? Why do we always have to be so meticulous about sanity checks?

It’s such a simple principle, yet so many people have overlooked it: it all boils down to that in order to be a “lazy programmer”, one that is different from a “hardworking programmer” who writes hundreds of lines of code for a simple program and spends days debugging it. Writing messy code to save time on the spot and then debugging like you’re trying to find that one needle in the bottom of the ocean is pure suicide. We need to be aware of those tools and keep looking for the best way to be efficient and save more time and effort in the long-term, thus being “lazy” in the smartest way possible.

After reading this column, I’m convinced that every college computer science student deserves to be fed all the knowledge in this column right after they finish any kind of “fundamentals of computing” classes because I’ve already made countlessly many connections to my data structures, discrete math, and assembly classes.

 

 

Programming Pearls Col 3 – Data Structures

Column 3 talked about how to design a program to be as clean and efficient as possible using data structures. After all data structures are the building blocks of any system.

Important topics (all about writing good code => good programs!)

-Separation of data from logic: reusable code when data changes

E.g. Tax bracket problem

-Object-oriented design: encapsulated objects => more readable, maintainable code

-Data structures and data representation:

E.g. arrays, containers, databases, etc.

Programming Pearls Col 2 – Aha! Algorithms

Column 2 introduced models to solutions to the classical “group anagrams”, “string rotation” and “finding duplicates” problems. The author used very simple mathematical principles to design solutions and called them aha! insights. Then variations to the principles are applied in the implementation of the solution in regards to the problem.

Group anagrams: using a signature for each group of anagrams (sorting one of the anagrams and using as key to bucket in hash map)

String rotation:

  1. x modulo n – x is the length of the string and n is the number of rotations. This solution ends up using constant memory and linear time. But it only works when x is divisible by n. (slow in time, efficient in memory)
  2. Reversal: String as ab, a is characters [0, i). Place a in its final position, then reverse the rest recursively. (spikes in intervals)
  3. Block reverse: Separate string into a and b and reverse recursively: in every step, reverse a to get a’, reverse b to get b’, and (a’b’)’ to obtain ba. Apply this principle to convert three partitions (abc to cba) – reverse either ab or bc, reverse the rest, then reverse the whole string. (fastest long-term)

Finding duplicates:

  1. Extracting a small portion of data each time to use binary search on it. This solution has stable performance.
  2. Another solution I was thinking is XORing bit patterns and output the first bit pattern that outputted 0. Although its worst case is O(N), it can potentially reach the goal faster than binary search in some cases

Programming Pearls Col 1 – Cracking the Oyster

Before starting to read Programming Pearls, I have never seriously considered the true importance of approaches stemmed from algorithms. Whenever I tried my hands on harder problems on LeetCode, I’ve always thought that coming up with an optimal solution in the blink of an eye is an activity reserved to only the geniuses and the brightest of them all.

But after just reading col. 1 from Programming Pearls, I realized how forgetful I am of all the power I have from the knowledge of algorithms. And from asking a simple question as “How do I sort a disk file?”, the approach of asking the right questions and framing a problem properly is not reserved to computer science Ph.D.’s only – everyone should be able to do so.

Consider the file sorting problem. We ask some questions first to make proper assumptions about data: What is the input? What is the desired output? What is the data? What are the constraints on the data? How big is the input file? What are the time and memory constraints?

As soon as we have answers to these questions, we formally define the problem by listing the input, output, and constraints.

Now we begin to construct several solutions and compare them. In this case, solutions using merge sort (time-efficient) and a multipass sort (memory-efficient) were proposed.

Some may stop here and pick one to end problem-solving process, but we can even dream bigger and go further, because we haven’t exploited all the conditions we have.  Can we do better than O(nlogn) sorting with non-specialized data? No. But can we save space by compressing data (representing data in a different way)? Definitely.

Then we arrive at the bitmap representation of numbers. Since the file contains unique numbers only, this satisfies the requirements for our problem. This marks the end of the disk file sorting problem, but there are many other considerations left to explore for the reader.

What was especially interesting to me were the design problems proposed at the end of the chapter. These are questions designed to challenge how the reader, after being inspired by the disk file sorting problem, thinks about other tricky problems. I have been afraid of the large scope of a design-oriented problem, but this chapter encouraged me to think about all the tools I have at hand to propose as many solutions as possible and compare them at the end.

~Moving over to Devpost for my current and future hackathon/side projects~

I’ve decided to migrate to Devpost entirely for future projects, since I’ve been working on bigger team and collaborative projects lately. Devpost is by far the easier and cleaner way to organize relevant information (e.g. logistics, responsibilities of teammates, the fact that the project description was crafted by the whole team, etc.) than posts on my personal blog.

See my Devpost profile~~~ https://devpost.com/jluo9612

With that said I will dedicate my blog as a place where I gather learning resources and share my thoughts on things from now on.

Why is Wi-Fi so much slower than wired connections?

Wi-Fi is probably used a lot more commonly these days than wired connections. The wireless 802.11 protocol was actually based on the Ethernet protocol (802.3).

Because data transmission processes are all decentralized, multiple access protocols are needed to minimize the number of collisions when there are a large number of hosts. There were the O.G.’s like Pure ALOHA, but CSMA/CD is probably the best protocol used for Ethernet connections.

But why doesn’t 802.11 also use CSMA/CD? This is because Wi-Fi devices use radio waves, and because of huge frequency differences between send frequencies and receive frequencies, they cannot send and receive at the same time. Thus Collision Detection (CD) becomes unviable.

This exact property slows down Wi-Fi performance because Wi-Fi uses Collision Avoidance (CA) and involves a lot of wait time periods for requests-to-send and permissions-to-send back-and-forth.

Knowledge from this reading: https://hpbn.co/wifi/#

Browser rendering and performance

In order to deliver one web page, a ton of hard work needs to be done in the browser. As developers having a good understanding of how the browser works gives us insights into how to optimize performance. Here are some study notes I took. Hats off to browser developers!!!

The rendering a webpage in the browser can be broken down into 4 steps:

1. Parsing:

HTML and CSS are parsed to construct parse trees, which will be turned into DOM trees.

HTML is forgiving syntax-wise for better browsing experiences. Even if tags are not closed the browser will recognize tags and construct a parse structure tree with all tags. This is done through the tokenizer, which recognizes symbol characters as special things like a “start tag”.

Things like <script>, <link> and <style> JavaScript/CSS specified in HTML can halt the parser from continuing to parse the rest of the HTML.

Performance insight: But because modern browsers will look for these tags, fetch and process any external scripts, images and stylesheets in a multi-threaded manner, it’s considered best practice to always include JavaScript and CSS externally. There is an exception for CSS, though. Since inline CSS has the highest priority, inline CSS will always be parsed prior to other CSS. One can use this property to improve the speed of CSS parsing/rendering.

If JavaScript changes the DOM structure, such as adding an element, HTML needs to be re-parsed and that takes more time.

2. Form Render Object tree:

This maps the respective nodes, styles of the nodes, and boxes of elements in the DOM.

3. Layout:

Once browser gets the render tree it starts constructing the layout according to this tree. It will traverse each render object recursively, laying out children first, and then parent elements.

If the user interacts with the page and cause changes, browser will detect changes and apply in batches. But if the changes are large-scale, for example, font changes and browser resizing, the layout will have to be reconstructed and that slows down rendering a lot.

Performance insight: The JavaScript best practice is to batch all reads and all writes separately to avoid having to re-layout a lot of things every step of the way.

4. Painting:

RenderLayers is constructed from RenderObject. It produces layers to correctly display the position, transparency, etc. of the nodes. There can be multiple nodes on the same layer depending on their CSS properties.

Performance insight: The browser will utilize the GPU to produce bitmaps of each layer to be displayed on the user’s screen.

Similar to scalable temporal video coding, the problem of re-layout delay can be solved by “delta last bitmap”, comparing last to current bitmaps so that it only needs to re-draw a small portion of the page.

The rendering process is a constantly ongoing loop, since the user will constantly be interacting with the page in session. There are also a lot of tips and tricks as to how to optimize browsing experience, such as using fixed height, delaying/asyncing scripts and stylesheets to speed up first paint, etc.

 

An interesting interview experience with a startup

I came across a local startup (A) during the Fall career fair at my school, talked to a lady who represented A. She said she was very impressed with my experiences and projects, however since they are mainly looking for potential returners, I, as a sophomore, would have to have lower priority than upperclassmen. I agreed and returned home afterward. About two weeks later, I was contacted by another recruiter, S, from the same company A, to schedule a phone screen.

Phone screen went well. Nothing happened until I followed up with S two weeks later. S immediately thanked me for the followup and said A has been integrating a coding challenge for their candidates but is now done and can move on.

Completed the coding challenge. Again, absolute silence from S until I followed up the second time. Then S went on and scheduled a final video interview for me with two engineers.

Up to this point, a month has passed. I’ve always replied immediately to S’s emails when they came. I had a pleasant conversation with the engineers over the video chat and they told me I’m a top candidate.

Two hours later, S called with a verbal offer, then went over some things like compensation and benefits, which they don’t offer for interns. To be honest, at that moment I didn’t feel very excited about this offer already. So I told S I’m far into another interview process. S said the deadline is in three days but it is negotiable if things change. I felt a bit pressure coming from the other end of the phone but I didn’t think too much about it at the time.

Then S called two days after, updating me on some minor stuff. I told him honestly that I think the compensation is too low compared to the software engineer average salary in the area. He began to sound impatient, cutting me off whenever I tried to explain about my relocation concerns and answered: “No we don’t offer any benefits for interns”.

Two days later, the offer letter came. At the bottom of the letter, there’s the HR’s contact info for questions and concerns. I felt it could speed things up if I reached out directly for a salary negotiation so I decided to shoot an email to the HR.

Out of courtesy, I CC’d S in that email. I even ringed S’s phone three times. S picked up the phone the third time but said that there was another call and quickly hanged off with impatience. I waited for S to call back.

Blahblahblah….

Here’s when things got interesting: S called back, immediately began raising their voice and chastising me for my “highly unprofessional and disrespectful” behavior to send that email to the HR. The very first thing S said was they “understand that I was inexperienced” and S, as a veteran recruiter with 15 years of experience, had never seen this behavior more than twice.

Then I was silenced by S for about 2 minutes. I was stunned. Although I did wonder if my behavior was against etiquette, I realized that S was being unreasonable. Well, if it’s only for employees, why was the email included in an offer letter? I decided to assert myself. I asked why and S said that contacting HR is only allowed for employees. I explained firmly that I was only exercising my right to know before a decision to accept the offer. S ignored my appeal and went onto talking about how unprofessional I was.

At this point, I felt it was pointless to argue with this person so I apologized to S. S began to compromise a little bit but still continued to chastise me and asserting their 15 years of experience…

I decided to decline the offer.

So this week, after messaging one of the engineers on LI informing him that I declined the offer, S called me again. I wondered again why S was calling me even at this point that I clearly showed disinterest in accepting the offer or ever conversing with them again. Well, as a seasoned professional working in the tech industry, S is clearly showing a lot of professionalism by calling me now to ask why I decided to decline and probably after saying that I was their “top candidate”. If it was what I thought it was, I’m done with S, and company A which hired S as their university recruiter.