However, links between France and Algeria remain difficult and fractured, fifty years after Algeria gained independence after a bloody civil war. Plus, the legacy of more than 130 years of France's often brutal colonial rule in the North African country poses a continuing stumbling block to strong, uncomplicated ties.
"We hope that the visit of Francois Hollande will mark a new stage in our bilateral relations which are expected to deepen," Bouteflika said, obviously seeking warmer relations after five years of Nicolas Sarkozy, who was widely unpopular in North Africa.
International Business Times spoke to an expert on French politics to sort out Franco-Algerian relations and what the Hollande-Bouteflika summit can hope to accomplish.
Douglas Yates is a professor of political science at the American Graduate School in Paris as well as The American University of Paris.
IB TIMES:How, if at all, will Hollande change his policies towards Algeria compared to his predecessor, Sarkozy?
YATES: There are few expectations here in France that François Hollande will fundamentally change government policy towards Algeria, given the many long-term, structural relations between the two countries. Algeria is an important supplier of petroleum, and a strategic partner in the war on terror in the region.
But there has been a change of emphasis, that is, from President Sarkozy's visible support for Morocco to President Hollande's support for Algeria.
Some have even spoken of a "pro-Algerian" lobby within the Elysée Palace, including the agriculture minister Stéphane Le Foll, the minister for veterans Kder Arif, and the presidential advisor for diversity, Faouzi Lamdaoui. All three have participated in official trips that Hollande made to Algeria when he was head of the Socialist Party.
Recently, Hollande communcated his desire to "reinforce the partnership" between the two countries, and, for the first time, a French president will make an official voyage to Algeria before going to Morocco.
IB TIMES:Does the Paris government ever pressure Algerian president Bouteflika to ease his repressive policies?
YATES: France does not do much to pressure the Algerian government, in part because there is little it can do, and in part because it needs Algeria's police state to squeeze information out of Islamicist terrorists.
There is little France can do because of the long, bloody war of independence that left France without much credibility with the Algerian population, compounded by its decades-long collaboration with the ruling National Liberation Front (FLN) regime in Algiers.
But also, much of the repression by the Algerian state has been concentrated on Islamists, a common enemy, who fought a long and bloody civil war against the FLN regime which resulted in an estimated 200,000 deaths since 1991, when the Front Islamique de Salut (FIS) won the first round of legislative elections before the military annuled the results.
IB TIMES:Is Algeria an important trade partner for France?
YATES: Yes, in addition to a regular flow of oil across the Mediterranean, there are 450 French businesses installed in Algeria, including some major French corporations. For example, the French oil giant Total S.A. (NYSE: TOT) runs a major petrochemicals refinery and the French automobile manufacturer Renault SA (EPA:RNO) operates a car factory in Oran.
In addition, the French pharmaceutical giant Sanofi SA (NYSE: SNY) runs a factory and French engineering firm Alstom SA (EPA: ALO) operates a tramway in Algiers.
The two countries combine geographical, historic and demographic ties that could best be described as a form of “complex interdependence.”
IB TIMES:Do you think Boutelfika and Hollande will discuss immigration, or is that now a dead topic?
YATES: Immigration is not a dead topic, but it has evolved significantly over the past two decades.
There are large numbers of French citizens of Algerian origin who regularly shuttle between Paris and Algiers, and fifty years after de-colonization, the contacts between the two societies are rich and complex.
But the new wave of North African immigrants into France have not come from Algeria, but from Tunisia.
If there is a problem with illegal immigration and the regularization of immigrants, it is with those fleeing countries that suffered regime collapse during the Arab Spring.
The immigration problem in Algeria has developed into one concerning the use of Algeria as a transhipment point from sub-Saharan Africa into Europe, rather than the older issue of Arabo-Berber migrants leaving for France.
Here the regime in Algiers can actually present itself as a partner in controlling immigration into Europe.
IB TIMES: Is there a strong Algerian opposition movement within France itself?
YATES: The large number of "French of Algerian origins," (which is the way they are classified in the census, because French law does not permit racial categories in the census), of course, contains many opponents of the FLN regime.
Some of these are Berbers, the indigenous peoples of Algeria who have lived in the region since Antiquity.
It is difficult to overestimate the importance of France to the Berbers. Most academic knowledge of Kabyle (the Berber language) is produced in Paris.
Here, in Paris, is the only Berber television station. Most Berber websites are based here, and most Berber books are edited or re-edited here. Indeed, the Académie Berbère, and the Groupe d'Etudes Berbères are based at the University of Paris VIII, while the Bulletin d'Etudes Berbères denounces militant Arabs from here.
But the most dangerous opposition to the ruling FLN are not the Berbers, but the Islamists.
These Islamic fundamentalists are present on French soil, but are not welcomed.
The presence of the fundamentalist opponents of the FLN regime in France provide a common incentive for cooperation between the French government and the Algerian regime. If you like, Franco-Algerian relations could be simplified as Algiers helps Paris fight Islamic terrorists in the Sahara and the Sahel, while Paris helps Algiers contain Islamic opposition organizations in Europe.
It is a symbiotic relationship that makes the two governments complicit, and makes fundamental policy change under President Hollande unlikely.