Introduction to Algorithms

I was recently searching for a good website for studying Algorithms. After going through various websites, I stumbled upon this educative.io course.

I was immediately hooked upon seeing the quality of the study material and that how easy it is for anyone to start learning. Course material are very visual with lots of explanations, pictures and demos.

It is divided into sub sections as follows –

 

 

 

 

 

 

 

 

 

 

 

Website – https://www.educative.io

 

And no, this post is not sponsored or anything. As I found it useful for myself and so I have shared. Pass it on and help others learn if you have too.

 

 

Writing Clear Code – Java Style

The overarching goal when writing code is to make it easy to read and to understand. Well-written programs are easier to debug, easier to maintain, and have fewer errors. Writing a program is a lot like writing an essay. When writing an essay, your message is more convincing when it is accompanied by proper grammar and punctuation. When writing computer programs, you should follow the same principle. It is even more important when programming since someone may be assigned to maintain and support your code for long periods of time. You will appreciate the importance of good style when it is your task to understand and maintain someone else’s code!

Coding.

  • Keep programs and methods short and manageable.
  • Use language-specific idioms.
  • Use straightforward logic and flow-of-control.
  • Avoid magic numbers (numbers other than −1, 0, 1, and 2); instead, give them meaningful symbolic names.

Naming conventions.

Here are some general principles when choosing names for your variables, methods, and classes.

  • Use meaningful names that convey the purpose of the variable. Choose names that are easy to pronounce, and avoid cryptic abbreviations. For example, use wagePerHour or hourlyWage instead of wph. Use polygon instead of p or poly or pgon.
  • Be consistent.
  • Name boolean variables and methods so that their meaning is unambiguous, e.g., isPrime or isEmpty() or contains().
  • Use shorter names (e.g., i) for short-lived variables and loop-index variables. Use more descriptive names for variables that serve an important purpose.
  • Avoid generic names like foo or tmp and meaningless names like fred. Use terminology from the application domain when possible.
  • Name a constant by its meaning, not its value, e.g., name your variable DAYS_PER_WEEK instead of SEVEN.
IDENTIFIER NAMING RULES EXAMPLE
Variables A short, but meaningful, name that communicates to the casual observer what the variable represents, rather than how it is used. Begin with a lowercase letter and use camel case (mixed case, starting with lower case). mass
hourlyWage
isPrime
Constant Use all capital letters and separate internal words with the underscore character. BOLTZMANN
MAX_HEIGHT
Class A noun that communicates what the class represents. Begin with an uppercase letter and use camel case for internal words. class Complex
class Charge
class PhoneNumber
Method A verb that communicates what the method does. Begin with a lowercase letter and use camelCase for internal words. move()
draw()
enqueue()

Commenting.

Programmers use comments to annotate a program and help the reader (or grader) understand how and why your program works. As a general rule, the code explains to the computer and programmer what is being done; the comments explain to the programmer why it is being done. Comments can appear anywhere within a program where whitespace is allowed. The Java compiler ignores comments.

  • Line comments. An end-of-line comment begins with // (two forward slashes) and ends at the end of the line on which the forward slashes appear. Any text from the // to the end of the line is ignored.
  • Block comments. A block comment begins with /* (a forward slash and asterisk) and ends with */ (asterisk and a forward slash). Any text between these delimiters (even if it spans multiple lines) is ignored.
  • Bold comments. A bold comment is a special case of a block comment designed to draw attention.
    /*---------------------------------------------------------
     *  Here is a block comment that draws attention
     *  to itself.
     *---------------------------------------------------------*/
    
  • Javadoc comments. A Javadoc comment is a special case of a block comment that begins with /** (a forward slash and two asterisks). They are typically used to automatically generate the API for a class. Here are guidelines for writing Javadoc comments.

There is no widely agreed upon set of rules. Good programmers write code that documents itself.

  • Make sure that comments agree with the code. Be careful to update the comments when you update the code.
  • Do not write comments that merely restate the code. Generally, comments should describe what or why you are doing something, rather than how.
    i++;      //  increment i by one
    
  • Comment any potentially confusing code, or better yet, rewrite the code so that it isn’t confusing.
  • Include a bold comment at the beginning of each file with your name, date, the purpose of the program, and how to execute it.
    /*----------------------------------------------------------------
     *  Author:        Kevin Wayne
     *  Written:       5/3/1997
     *  Last updated:  8/7/2006
     *
     *  Compilation:   javac HelloWorld.java
     *  Execution:     java HelloWorld
     *  
     *  Prints "Hello, World". By tradition, this is everyone's
     *  first program.
     *
     *  % java HelloWorld
     *  Hello, World
     *
     *----------------------------------------------------------------*/
    
  • Comment every important variable name (including all instance variables) with a // comment, and align the comments vertically.
    private double rx, ry;    //  position
    private double q;         //  charge
    
  • Comment each method with a description of what it does. Include what it takes as input, what it returns as output, and any side effects. Use the parameters names in your description.
    /**
     *   Rearranges the elements in the array a[] in random order
     *   using Knuth's shuffling algorithm.
     *
     *   Throws a NullPointerException if a is null.
     */
    public static void shuffle(String[] a)
    

Whitespace.

Programmers use whitespace in their code to make it easier to read.

  • Don’t put more than one statement on a line.
  • Use blank lines to separate your code into logical sections.
  • Put a space between all binary operators (e.g., <=, =, +) and their operands. One possible exception is to emphasize precedence.
    a*x + b
    
  • Include a space between a keyword (e.g., while, for, if) and its opening parenthesis.
  • Put a space after each statement in a for loop.
    for(int i=0;i<n;i++)    vs.      for (int i = 0; i < n; i++)
    
  • Put a space after each comma in an argument list.
  • Put space after each comment delimiter.
        //This comment has no space           //  This comment has two 
        //after the delimiter and is          //  spaces after the delimiter
        //difficult to read.                  //  and is easier to read.
    
  • Do not put spaces before a semicolon.
  • Do not put spaces between an object name, the . separator, and a method name.
  • Do not put spaces between a method name and its left parenthesis.
  • Include blank lines to improve readability by grouping blocks of related code.
  • Use spaces to align parallel code whenever it enhances readability.
    int n      = Integer.parseInt(args[0]);      //  size of population
    int trials = Integer.parseInt(args[1]);      //  number of trials
    

Indenting.

Programmers format and indent their code to reveal structure, much like an outline.

  • Avoid lines longer than 80 characters.
  • Do not put more than one statement on a line.
  • Indent a fixed number of spaces. We recommend 3 or 4.
  • Always use spaces instead of tabs. Modern IDEs (including DrJava) insert spaces when you type the tab key – these are known as soft tabs. Hard tabs are obsolete: in ancient times, they were used for data compression.
  • Use a new indentation level for every level of nesting in your program.
  • Follow either the K&R or BSD/Allman indentation styles for curly braces, and use it consistently. We consistently use the former for the booksite and the latter in the textbook.
    //  K&R style indenting                   
    public static void  main(String[] args) {
        System.out.println("Hello, World");
    }
    
    //  BSD-Allman style indenting
    public static void main(String[] args)
    {
        System.out.println("Hello, World");
    }
    

 

Content picked up from this site.

Beware of this new phishing attack

A Chinese information security researcher has reported about an “almost impossible to detect” phishing attack that can be used to trick even the most careful users on the Internet.

He warned, hackers can use a known vulnerability in the Chrome, Firefox and Opera web browsers to display their fake domain names as the websites of legitimate services, like Apple, Google, or Amazon to steal login or financial credentials and other sensitive information from users.

What is the best defence against phishing attack? Generally, checking the address bar after the page has loaded and if it is being served over a valid HTTPS connection. Right?

Okay, then before going to the in-depth details, first have a look at this demo web page (note: you may experience downtime due to high traffic on demo server), set up by Chinese security researcher Xudong Zheng, who discovered the attack.

It becomes impossible to identify the site as fraudulent without carefully inspecting the site’s URL or SSL certificate.” Xudong Zheng said in a blog post.

If your web browser is displaying “apple.com” in the address bar secured with SSL, but the content on the page is coming from another server (as shown in the above picture), then your browser is vulnerable to the homograph attack.

There is another proof-of-concept website created by security experts from Wordfence to demonstrate this browsers’ vulnerability. It spoof “epic.com” domain.

Homograph attack has been known since 2001, but browser vendors have struggled to fix the problem. It’s a kind of spoofing attack where a website address looks legitimate but is not because a character or characters have been replaced deceptively with Unicode characters.

Many Unicode characters, which represents alphabets like Greek, Cyrillic, and Armenian in internationalized domain names, look the same as Latin letters to the casual eye but are treated differently by computers with the completely different web address.

For example, Cyrillic “а” (U+0430) and Latin “a” (U+0041) both are treated different by browsers but are displayed “a” in the browser address.

Punycode Phishing Attacks

unicode-phishing-attack

By default, many web browsers use ‘Punycode’ encoding to represent unicode characters in the URL to defend against Homograph phishing attacks. Punycode is a special encoding used by the web browser to convert unicode characters to the limited character set of ASCII (A-Z, 0-9), supported by International Domain Names (IDNs) system.

For example, the Chinese domain “短.co” is represented in Punycode as “xn--s7y.co“.

According to Zheng, the loophole relies on the fact that if someone chooses all characters for a domain name from a single foreign language character set, resembling exactly same as the targeted domain, then browsers will render it in the same language, instead of Punycode format.

This loophole allowed the researcher to register a domain name xn--80ak6aa92e.com and bypass protection, which appears as “apple.com” by all vulnerable web browsers, including Chrome, Firefox, and Opera, though Internet Explorer, Microsoft Edge, Apple Safari, Brave, and Vivaldi are not vulnerable.Here, xn-- prefix is known as an ‘ASCII compatible encoding’ prefix, which indicates web browser that the domain uses ‘punycode’ encoding to represent Unicode characters, and Because Zheng uses the Cyrillic “а” (U+0430) rather than the ASCII “a” (U+0041), the defence approach implemented by web browser fails.

Zheng has reported this issue to the affected browser vendors, including Google and Mozilla in January.

Punycode Phishing Attacks
Fake Page (top) and Original Apple.com (bottom), but exactly same URL

While Mozilla is currently still discussing a fix, Google has already patched the vulnerability in its experimental Chrome Canary 59 and will come up with a permanent fix with the release of Chrome Stable 58, set to be launched later this month.

Meanwhile, millions of Internet users who are at risk of this sophisticated hard-to-detect phishing attack are recommended to disable Punycode support in their web browsers in order to temporarily mitigate this attack and identify such phishing domains.

How to Prevent Against Homograph Phishing Attacks

Firefox users can follow below-mentioned steps to manually apply temporarily mitigation:

  1. Type about:config in address bar and press enter.
  2. Type Punycode in the search bar.
  3. Browser settings will show parameter titled: network.IDN_show_punycode, double-click or right-click and select Toggle to change the value from false to True.

Unfortunately, there is no similar setting available in Chrome or Opera to disable Punycode URL conversions manually, so Chrome users have to wait for next few weeks to get patched Stable 58 release.

Although, there are some third-party Chrome extensions/add-ons available on App Store that users can install to get alerts every time they came across any website with Unicode characters in the domain.

Meanwhile, one of the best ways to protect yourself from homograph attacks is to use a good password manager that comes with browser extensions, which automatically enter in your login credentials for the actual domains to which they are linked.

So, whenever you came across any domain which looks like legitimate “apple.com” or “amazon.com” but actually is not, your password manager software will detect it and will not automatically authenticate you to that phishing site.

Moreover, Internet users are always advised to manually type website URLs in the address bar for important sites like Gmail, Facebook, Twitter, Yahoo or banking websites, instead of clicking any link mentioned on some website or email, to prevent against such attacks.

A simple way to limit the damage from bugs such as this is to always use a password manager. In general, users must be very careful and pay attention to the URL when entering personal information. Until this is fixed, concerned users should manually type the URL as stated above or navigate to sites via a reputed search engine when in doubt. This is a serious vulnerability because it can even fool those who are extremely mindful of phishing.
Pass this post on and let others know about this too.  It may save someone from falling prey unknowingly to an hacker.
Content for this blog post was sourced from this post and this is researcher’s original blog post.

How are passwords stored?

Have you ever wondered how do websites store passwords?

Why can’t a Facebook or a Google employee copy your password and regain access to your account? Or why some websites tell you to set a new password, instead of sending you your forgotten password whenever you click ‘Forgot your password?’.

It’s because most websites nowadays don’t save passwords in plain text, instead save its algorithmic computed hash. Whenever you log in with a password, it is hashed and then compare the resultant hash with the one in the database. That means any attacker that gets to their database will only see the hash of your password, not the real one.

Rule-of-thumb: if you forget your password and the website sends it back to you in plain text, then that’s how they store it. You should make sure you’re not using that password anywhere else and also never to use that site again.

But what is a hash?

A hash is the output of a one-way function that takes an input and maps it to a fixed-length string that works as a unique signature for the given input and is ideally never produced with any other input (Wikepedia). The important properties of a hash function are that it is –

  1. Deterministic (same input gives the same hash every time)
  2. Practically impossible to generate the same hash from two different inputs
  3. It is impossible to get the input from the hash unless you try every possible input.
  4. Any change to the input, however small, would make the resulting hash unrecognizable from the original input’s hash. Examples of a hash function include MD5 (broken), SHA-1 (not recommended) and SHA-3 (recommended standard).

 

hashing-11-638

 

During verification –

hashing-12-638

Unfortunately, many people can use the same passwords, and because hash functions are deterministic, it means that the hashes of those passwords would be the same. That means if a passwords database were compromised, and you know the password of one user, you could also gain access to whoever has the same password (because the hashes are the same).

 

Enter salts

Salts are random data that are unique to each user, which are added to the user’s password before hashing it. Because of the 4th property of a good hash, the new hash is unrecognizable from the old one, thus even if user X and Y use the same password because X and Y have different, unique salts, the hash of each user’s password would look completely different. A salt can be publicly stored in plain text, as it’s just random data that doesn’t provide any insight on the user’s password.

Below image will help in understanding further –

Hash-plus-Salt

In simpler terms –

Salting

 

Pass it on and help others learn if you have too.  Thanks.

 

This was sourced from this original post. If you are a developer and further interested in securing passwords, this thread on stack exchange is for you to further read.

Browser setting to turn off right now

Modern day browser’s have a very useful feature in-built which is the auto-fill. It can assist a user by automatically filling in forms and other important fields without user needing to manually enter the data each time. It is a one time process thereby after which browser can pre-fill the stored user data onto the form each time user visits a site requiring a form fill-up, sign-up process or finishing online purchases by entering credit card and other crucial details.

It is a very useful feature indeed but with a very serious security problem. As demonstrated by a Finnish developer Viljami Kuosmanen, users can easily fall into hacker’s trap if they use autocomplete feature on unknown websites. Scammers have found a sneaky way to retrieve the stored information using autocomplete feature.

Scammers could simply add additional “hidden” boxes to the page, and trick people into giving away more info than they intended to. Users think they’re just entering their name and email address, but “hidden” text boxes are automatically filled in with more sensitive data like address, phone number, and credit card number.

Below is the demonstration given by Viljami as a proof of concept –

Affected browsers include big shots like Chrome, Safari, and Opera, as well as extensions like the password manager/form filler LastPass, which is perhaps an even more obvious target. So, if you’re currently using any of these, it’d be wise to head to your Preference menu and temporarily disable the auto-fill feature until a security patch is pushed out. To deactivate the feature in Chrome, go to Settings, Advanced Settings, and uncheck the boxes beneath Passwords and Forms. Stay safe folks.

Here is the image after successfully retrieving the full user info taken from the above –

browser-settings

 

 

Pass this post on and let others know about this too.  It may save someone from falling prey unknowingly to an hacker.

Java Programming Cheatsheet

Here is the quick reference for Java Programming I found on the web. It summarizes common features and usage in shortest and easiest way possible. 

This is just a blog post taking useful content from Princeton University’s site. For the good intend to share the knowledge with other users and programmers. No intention of modifying or removing credits. Just thought to share this awesome resource with everyone. For more in depth reference, above link to university’s website is advised. It is well documented with excellent documentation and programming examples. 

Hello, World.

Hello, World in Java

Editing, compiling, and executing.

Compiling Hello, World in Java

Built-in data types.

Built-in types of data

Declaration and assignment statements.

Assignment statements

Integers.

int data type

Integer expressions

Floating-point numbers.

double data type

double expressions

Booleans.

boolean data type

Boolean operators

Comparison operators.

Comparison operators

Comparison examples

Printing.

System.out.print()

Parsing command-line arguments.

parsing Command-line arguments

Math library.

Math library API

Java library calls.

Expressions that use Java library methods

Type conversion.

Type conversion

Anatomy of an if statement.

anatomy of an if statement

If and if-else statements.

If-else statements

Nested if-else statement.

Nested if-else statements in Java

Anatomy of a while loop.

While loop

Anatomy of a for loop.

For loop

Loops.

While and for loops in Java

Break statement.

Break statement in Java

Do-while loop.

Do-while loop in Java

Switch statement.

Switch statement in Java

Arrays.

An array

Inline array initialization.

Inline initialization of arrays

Typical array-processing code

Two-dimensional arrays.

2D array

2D array inline initialization

standard output library.

Standard output API

Anatomy of printf

Formatting codes for printf

standard input library.

Standard input API

standard drawing library.

Standard drawing API

standard audio library.

Standard audio API

Command line.

command line

Redirection and piping.

Redirecting standard output                Redirecting standard input

Piping

Functions.

Anatomy of a function

Example functions

Libraries of functions.

Library abstraction

standard random library.

Standard random

standard statistics library.

Standard statistics

Using an object.

Using an object

Instance variables.

Anatomy of instance variables

Constructors.

Anatomy of a constructor

Instance methods.

Anatomy of an instance method

Classes.

Anatomy of a class

Object-oriented libraries.

Object-oriented library abstraction

Java’s String data type.

String library API

String operations

Java’s Color data type.

Color library API

input library.

Input API

output library.

Output API

picture library.

Picture API

stack data type.

Stack API

queue data type.

Queue API

Iterable.

Anatomy of an iterable

symbol table data type.

Symbol Table API

set data type.

Set API

graph data type.

Graph API

 

 

Pass it on and help others learn if you have too.

Python Programming Cheatsheet

Here is the quick reference for Python Programming I found on the web. It summarizes common features and usage in shortest and easiest way possible.

There are also some Princeton University developed modules which are very useful. I have also included them with direct links to it’s corresponding webpage on University’s website.

This is just a blog post taking useful content from Princeton University’s site. For the good intend to share the knowledge with other users and programmers. No intention of modifying or removing credits. Just thought to share this awesome resource with everyone. For more in depth reference, above link to university’s website is advised. It is well documented with excellent documentation and programming examples.

So, here it goes –

 

Hello, World.

import stdio

# Write 'Hello, World' to standard output.
stdio.writeln('Hello, World')

Editing, compiling, and interpreting.

Editing, compiling, and interpreting Hello, World in Python

Built-in data types.

Built-in types of data

Assignment statements and traces.

Assignment statements trace Assignment statements formal trace

Strings.

Str data type

Integers.

Int data type

Floating-point numbers.

Float data type

Booleans.

Bool data type Boolean operators operators

Comparison operators.

Comparison operators

Common functions.

Common Python functions

Type conversion.

Type conversion API

if and if-else statements.

If-else statements

if-elif-else statements.

if   income < 0:      rate = 0.00
elif income < 8925:   rate = 0.10
elif income < 36250:  rate = 0.15
elif income < 87850:  rate = 0.23
elif income < 183250: rate = 0.28
elif income < 398350: rate = 0.33
elif income < 400000: rate = 0.35
else:                 rate = 0.396

while and for statements.

While and for loops

break statements.

while True:
    x = 1.0 + 2.0*random.random()
    y = 1.0 + 2.0*random.random()
    if x*x + y*y <= 1.0:
        break

Arrays.

suits = ['Clubs', 'Diamonds', 'Hearts', 'Spades']

An array

a = stdarray.create1D(n)
...
for i in range(n):
    stdout.writeln(a[i])
... 
for element in a:
    stdout.writeln(element)

Array operations.

Array operations

Array aliasing and copying.

Array aliasing Array copying

Two-dimensional arrays.

2D array 2D array initialization
a = stdarray.create2D(rowCount, colCount)
...
for i in range(rowCount):
    for j in range(colCount)):
        stdio.writeln(a[i][j])
...     
for row in a:
    for element in row:
        stdio.writeln(element)

 

Redirection and piping.

Redirecting standard input Redirecting standard output

Piping

Functions.

Anatomy of a function

Example functions

Modules.

Module abstraction

Module control flow

The str data type.

The str module

Defining a class.

Charge API

Charge class

Creating an object.

Creating an object

Using an object.

p = c1.potentialAt(.20, .50)

Special methods.

Special methods: arithmetic

Special methods: comparison

Special methods: functions

 

stdio module: writing functions.

Standard output API

Anatomy of printf

Formatting codes for writef

 

stdio module: reading functions.

Standard input API

stddraw module.

Stddraw drawing functions

Stddraw control functions

Stddraw shape functions

Stddraw text and color functions

Stddraw animation functions

stdaudio module.

Standard audio API

stdrandom module.

Standard random module

stdarray module.

Standard array module

stdstats module.

Standard stats module

Color data type.

Color API

Picture data type.

Picture API

InStream data type.

InStream API

OutStream data type.

OutStream API

 

 

Pass it on and help others learn if you have too.